)
打卡第五十六天
1道简单题+2道中等题
题目：
思路：将问题转换为：某公交车从第1900站做为起点，第2000站做为终点。第i个人表示从第birth[i]站上车，在第death[i] + 1站下车。
题目描述到生于1908年，死于1909年的人应当被列入1908年和1909年的计数,所以第death[i]站还需要记录，在下一站再减去。
定义res[]记录每站数组的人数变化，因为题目范围是1900到2000，定义数组大小为110个。遍历数组，res[birth[i] - 1900]表示第birth[i]站上一人，res[death[i] + 1 - 1900]表示第death[i] + 1站下一人。整理res[]数组，找到车上人最多的站。
代码：
class Solution {
public:int maxAliveYear(vector<int>& birth, vector<int>& death) {vector<int> res(110, 0);int n = birth.size(); // 总人数for(int i = 0; i < n; i++){res[birth[i] - 1900]++;// 出生年份：从这一年开始人口+1res[death[i] + 1 - 1900]--;// 死亡年份：从下一年开始人口-1，死亡当年这个人还活着，所以要从下一年开始减}int ans = 0; // 最大存活人数int ret; // 最大存活人数对应的年份索引for(int i = 1; i <= 101; i++){res[i] += res[i-1];// res[i]现在表示1900+i年的实际存活人数ans = max(ans, res[i]);// 更新最大存活人数}for(int i = 0; i <= 101; i++){if(ans == res[i]){ // 最大存活人数对应的年份ret = i; // 记录年份索引break; // 找到第一个达到最大存活人数的年份}}return ret + 1900;}
};
耗时≈一小时 明天继续