难度: Medium
给定 N 个人的出生年份和死亡年份，第 i 个人的出生年份为 birth[i]，死亡年份为 death[i]，实现一个方法以计算生存人数最多的年份。
你可以假设所有人都出生于 1900 年至 2000 年（含 1900 和 2000 ）之间。如果一个人在某一年的任意时期处于生存状态，那么他应该被纳入那一年的统计中。例如，生于 1908 年、死于 1909 年的人应当被列入 1908 年和 1909 年的计数。
如果有多个年份生存人数相同且均为最大值，输出其中最小的年份。
示例：
输入： birth = [1900, 1901, 1950] death = [1948, 1951, 2000] 输出： 1901
提示：
0 < birth.length == death.length <= 10000birth[i] <= death[i]运行时间: 35 ms
内存: 16.9 MB
class Solution:
def maxAliveYear(self, birth: List[int], death: List[int]) -> int:
minVal = min(birth)
maxVal = max(death)
diff = [0] * (maxVal - minVal + 2)
for b, d in zip(birth, death):
diff[b-minVal] += 1
diff[d-minVal+1] -= 1
ans = 0
for i in range(1, maxVal - minVal + 2):
diff[i] += diff[i-1]
if diff[i] > diff[ans]:
ans = i
return ans + minVal
该题解使用了一种称为'差分数组'的技巧来计算每一年的生存人数。首先，定义一个差分数组`diff`，其中`diff[i]`表示第`i`年相比于前一年生存人数的变化量。遍历每个人，将他们的出生年份在差分数组中增加1（表示从这一年开始，人数增加了一个），而在他们死亡年份的次年减少1（表示从这一年开始，人数减少了一个）。遍历完成后，通过累加差分数组来得到每一年的具体生存人数。在此过程中，寻找并记录生存人数最多的年份。如果多个年份的人数相同，则由于数组是按年份顺序处理的，会自然选择最小的年份。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def maxAliveYear(self, birth: List[int], death: List[int]) -> int:
# 寻找最小出生年和最大死亡年
minVal = min(birth)
maxVal = max(death)
# 初始化差分数组
diff = [0] * (maxVal - minVal + 2)
# 构建差分数组
for b, d in zip(birth, death):
diff[b-minVal] += 1 # 出生增加人数
diff[d-minVal+1] -= 1 # 次年减少人数
# 用于找出最多人数的年份
ans = 0
# 累计差分数组，求每年的实际人数并找出最大值
for i in range(1, maxVal - minVal + 2):
diff[i] += diff[i-1]
if diff[i] > diff[ans]:
ans = i
# 返回实际年份
return ans + minVal
在差分数组中，对于每一个人的出生年份`b`，数组在`b - minVal`的位置上加1，表示从这一年开始生存人数增加。而在死亡年份`d`的次年，也就是`d-minVal+1`位置上减1，这代表从这一年开始人数减少，因为这个人不再算在生存人数中。这种方法可以确保在人死亡的那一年他/她仍然被计入生存人数，而从下一年开始不再被计算。
数组长度为`maxVal - minVal + 2`是为了确保在差分数组中能够处理最大死亡年份`maxVal`的次年的人数变化。如果数组长度只有`maxVal - minVal + 1`，那么对于最大的死亡年份`maxVal`来说，其次年`maxVal - minVal + 1`的索引将超出数组的范围，造成数组越界错误。通过将数组长度设为`maxVal - minVal + 2`，可以安全地在`maxVal - minVal + 1`位置上操作，从而准确地处理所有年份的人数变化。
累加差分数组以计算实际人数时从索引1开始是因为索引0的位置已经是累加的结果，代表最小出生年份`minVal`的生存人数，即初始的人数变化。从索引1开始累加是为了更新差分数组，将每一年与前一年的人数变化累加，以此得到每一年的实际生存人数。如果从索引0开始，则会重复计算第一年的人数，导致错误的统计结果。