Cinte's Leetcode Record
0%

面试题 16.10. 生存人数

Posted on Edited on In Disqus:
Symbols count in article: 1.5k Reading time ≈ 1 mins.

面试题 16.10. 生存人数

dp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    int maxAliveYear(vector<int>& birth, vector<int>& death) {
        unordered_map<int, int> born;
        unordered_map<int, int> dead;
        for(auto& b : birth)
            ++born[b];
        for(auto& d : death)
            ++dead[d];
        vector<int> dp(102);
        dp[0] = 0;
        int maxLive = 0;
        int ret = 0;
        for(int i = 1; i <= 101; ++i)
        {
            int year = 1900 + i - 1;
            // 当年活着的人只需要计算前一年的人数加上今年出生的和去年死亡的
            // 注意，今年死亡的人数仍旧属于今年生存，所以需要放到下一年计算
            dp[i] = dp[i - 1] + born[year] - dead[year - 1];
            if(dp[i] > maxLive)
            {
                maxLive = dp[i];
                ret = year;
            }
        }
        return ret;
    }
};

改用数组

在栈上分配空间比堆上更加高效

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int maxAliveYear(vector<int>& birth, vector<int>& death) {
        int born[102]{ 0 };
        int dead[102]{ 0 };
        for(auto& b : birth)
            ++born[b - 1900 + 1];
        for(auto& d : death)
            ++dead[d - 1900 + 1];
        vector<int> dp(102);
        dp[0] = 0;
        int maxLive = 0;
        int ret = 0;
        for(int i = 1; i <= 101; ++i)
        {
            dp[i] = dp[i - 1] + born[i] - dead[i - 1];
            if(dp[i] > maxLive)
            {
                maxLive = dp[i];
                ret = 1900 + i - 1;
            }
        }
        return ret;
    }
};

差分数组，只记录每年的变化数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int maxAliveYear(vector<int>& birth, vector<int>& death) {
        int res[103]{ 0 };
        for(auto& b : birth)
            ++res[b - 1900 + 1];
        for(auto& d : death)
            --res[d - 1900 + 2];
        int maxLive = 0;
        int ret = 0;
        for(int i = 1; i <= 101; ++i)
        {
            res[i] += res[i - 1];
            if(res[i] > maxLive)
            {
                maxLive = res[i];
                ret = 1900 + i - 1;
            }
        }
        return ret;
    }
};