leetcode原题：生存人数-Toy模板网

这篇具有很好参考价值的文章主要介绍了leetcode原题：生存人数。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目：

给定 N 个人的出生年份和死亡年份，第 i 个人的出生年份为 birth[i]，死亡年份为 death[i]，实现一个方法以计算生存人数最多的年份。

你可以假设所有人都出生于 1900 年至 2000 年（含 1900 和 2000 ）之间。如果一个人在某一年的任意时期处于生存状态，那么他应该被纳入那一年的统计中。例如，生于 1908 年、死于 1909 年的人应当被列入 1908 年和 1909 年的计数。

如果有多个年份生存人数相同且均为最大值，输出其中最小的年份。

示例：

输入：
birth = [1900, 1901, 1950]
death = [1948, 1951, 2000]
输出： 1901

解题思路：

年份生存人数也就相当于是对每个年龄段的两头进行记录，找每个区间的重叠部分，返回重叠的最大值。

这里我们用到差分数组，出生年份的下标+1，死亡年份的下标-1

Code：文章来源地址https://www.toymoban.com/news/detail-690275.html

class Solution {
public:
    int maxAliveYear(vector<int>& birth, vector<int>& death) {
        int n = birth.size();
        vector<int> diff(2002, 0); // 定义差分数组diff
        //先将每个年龄段的两头确定出来，出生年份+1，死亡年份-1
        for (int i = 0; i < n; i++)
        {
            int x = birth[i], y = death[i];
            diff[x] += 1; diff[y+1]-=1; // 表示对区间[x, y]的元素全部加一
        }
        int max = 0, idx = 0, sum(0);
        //计算差分数组的前缀和，每一个前缀和对应问题的每一个位置的人数
        for (int i = 1900; i <= 2000; ++i) 
        {
            sum += diff[i];
            //更新生存人数最多的年份，（不加等号，就默认多个年份生存人数相同且均为最大值，输出其中最小的年份）
            if (max < sum)
            {
                max = sum; 
                idx = i;
            }
        }
        return idx;

    }
};

到了这里，关于leetcode原题：生存人数的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！