README.md

1854. 人口最多的年份

English Version

题目描述

给你一个二维整数数组 logs ，其中每个 logs[i] = [birthi, deathi] 表示第 i 个人的出生和死亡年份。

年份 x 的 人口 定义为这一年期间活着的人的数目。第 i 个人被计入年份 x 的人口需要满足：x 在闭区间 [birthi, deathi - 1] 内。注意，人不应当计入他们死亡当年的人口中。

返回 人口最多 且 最早 的年份。

 

示例 1：

输入：logs = [[1993,1999],[2000,2010]]
输出：1993
解释：人口最多为 1 ，而 1993 是人口为 1 的最早年份。

示例 2：

输入：logs = [[1950,1961],[1960,1971],[1970,1981]]
输出：1960
解释： 
人口最多为 2 ，分别出现在 1960 和 1970 。
其中最早年份是 1960 。

 

提示：

• 1 <= logs.length <= 100
• 1950 <= birthi < deathi <= 2050

解法

差分数组实现。

用 delta 数组记录每个人的出生和死亡年份。

题目中起始年份为 1950，我们希望数组的起始下标对应起始年份，并且年份与数组下标一一对应，因此我们需要引入起始年份与数组起始下标之差 offset=1950，使得下标 i 对应 i+offset 年。

遍历 logs 时，将每个人出生年份对应的变化量加上 1，同时将死亡年份对应的变化量减去 1。

最后，遍历 delta 数组，可以求出每一年的人口数量并维护其最大值和对应的最小下标 res。遍历结束后，将最小下标加上 offset，即是所求的年份。

Python3

class Solution:
    def maximumPopulation(self, logs: List[List[int]]) -> int:
        offset = 1950
        delta = [0] * 101
        # 遍历每个人的出生和死亡年份
        for birth, death in logs:
            # 出生年份人数+1
            delta[birth - offset] += 1
            # 死亡年份人数-1
            delta[death - offset] -= 1

        # mx表示人口数量最大值，cur表示当前年份人口数量，res表示人口数量最大的年份-offset
        mx = cur = res = 0
        for i in range(101):
            cur += delta[i]
            if mx < cur:
                mx = cur
                res = i
        return res + offset

Java

class Solution {
    public int maximumPopulation(int[][] logs) {
        int offset = 1950;
        int[] delta = new int[101];
        // 遍历每个人的出生和死亡年份
        for (int[] log : logs) {
            // 出生年份人数+1
            ++delta[log[0] - offset];
            // 死亡年份人数-1
            --delta[log[1] - offset];
        }
        
        // mx表示人口数量最大值，cur表示当前年份人口数量，res表示人口数量最大的年份-offset
        int mx = 0, cur = 0, res = 0;
        for (int i = 0; i < 101; ++i) {
            cur += delta[i];
            if (mx < cur) {
                mx = cur;
                res = i;
            }
        }
        return res + offset;
    }
}

JavaScript

/**
 * @param {number[][]} logs
 * @return {number}
 */
var maximumPopulation = function(logs) {
    const offset = 1950;
    const len = 2050 - 1950 + 1;
    let delta = new Array(len).fill(0);
    for (let log of logs) {
        delta[log[0] - offset] += 1;
        delta[log[1] - offset] -= 1;
    }
    let max = 0;
    let total = 0;
    let index = 0;
    for (let i = 0; i < len; i++) {
        total += delta[i];
        if (total > max) {
            max = total;
            index = i;
        }
    }
    return index + offset;
};

...