1.题目基本信息

1.1.题目描述

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

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

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

1.2.题目地址

https://leetcode.cn/problems/maximum-population-year/description/

2.解题方法

2.1.解题思路

差分数组

2.2.解题步骤

第一步，构建差分数组

第二步，升序遍历年份，求差分数组的前缀和，前缀和表示当前年的活着的人的个数，统计最大前缀和即为题解

3.解题代码

python代码

from collections import defaultdict

class Solution:
    def maximumPopulation(self, logs: List[List[int]]) -> int:
        # 思路：差分数组
        # 第一步，构建差分数组
        diff = defaultdict(int)
        for birth, death in logs:
            diff[birth] += 1
            diff[death] -= 1
        # 第二步，升序遍历年份，求差分数组的前缀和，前缀和表示当前年的活着的人的个数，统计最大前缀和即为题解
        sortedYears = sorted(diff.keys())
        # print(diff)
        maxPreSum = 0
        preSum = 0
        result = sortedYears[0]
        for year in sortedYears:
            preSum += diff[year]
            if preSum > maxPreSum:
                maxPreSum = preSum
                result = year
        return result

4.执行结果