LeetCode 面试题 16.10. 生存人数
题目描述
题意分析
第
i个人从birth[i]年到death[i]年都算存活，包括出生和死亡当年。统计 1900 到 2000 年中哪一年存活人数最多；若多个年份并列最多，返回其中最早的年份。
解法：差分数组 + 前缀和
核心思路
[!blue]
每个人为一个闭区间内的年份各贡献 1。直接逐年增加可以改成只记录变化：在出生年增加 1，在死亡次年减少 1。用
diff[i]表示1900 + i年相对前一年的净人数变化，再从早到晚累加即可恢复每年人数。对单个人来说，前缀和在出生前是 0，读到出生事件后变为 1，并一直保留到死亡当年；直到死亡次年的 -1 才抵消。因此它恰好在所需闭区间贡献 1。将所有人的变化相加，前缀和就得到总存活人数。
代码只扫描到 2000 年，死亡次年若已经是 2001 年，就不必记录这个减少事件，它不会影响任何待查询年份。每年先累加差分，再与此前峰值比较；只有人数严格更多时才更新年份，相同人数保持原记录，便能保留最早年份。
解题步骤
- 创建差分数组，用年份减去 1900 作为下标。
- 对每个人，在出生位置加 1；死亡次年仍处于统计范围内时，在对应位置减 1。
- 从 1900 年到 2000 年累加
alive，得到当前年的总存活人数。- 仅当
alive > bestAlive时更新峰值和年份，最后返回bestYear。
代码实现
class Solution {
public int maxAliveYear(int[] birth, int[] death) {
int[] diff = new int[102];
for (int i = 0; i < birth.length; i++) {
diff[birth[i] - 1900]++;
if (death[i] + 1 <= 2000) {
diff[death[i] + 1 - 1900]--;
}
}
int alive = 0;
int bestYear = 1900;
int bestAlive = 0;
for (int i = 0; i <= 100; i++) {
alive += diff[i];
// 年份递增扫描，同人数不更新，保留最早达到峰值的年份。
if (alive > bestAlive) {
bestAlive = alive;
bestYear = 1900 + i;
}
}
return bestYear;
}
}
func maxAliveYear(birth []int, death []int) int {
diff := make([]int, 102)
for i := 0; i < len(birth); i++ {
diff[birth[i]-1900]++
if death[i]+1 <= 2000 {
diff[death[i]+1-1900]--
}
}
alive := 0
bestYear := 1900
bestAlive := 0
for i := 0; i <= 100; i++ {
alive += diff[i]
// 年份递增扫描，同人数不更新，保留最早达到峰值的年份。
if alive > bestAlive {
bestAlive = alive
bestYear = 1900 + i
}
}
return bestYear
}
复杂度分析
- 时间复杂度：$O(n+Y)$。每人只记录两个变化，再扫描
Y = 101个年份。- 空间复杂度：$O(Y)$。年份范围固定，所以本题辅助空间为常数级。
关键点总结
[!green]
- 差分记录人数变化，前缀和恢复每年的实际人数。
- 死亡当年仍算存活，减少事件必须放在下一年。
- 升序扫描并且只在严格更大时更新，共同保证答案年份最早。
易错点总结
[!yellow]
- 在死亡当年减 1，会把该年仍应计入的人漏掉。
- 必须先加上当前年差分，再判断人数，否则会把事件错算到下一年。
- 相同人数也更新年份，会把最早峰值替换为更晚年份。
- 数组下标需要减去 1900，返回年份则要加回 1900。
- 2000 年也在统计范围内，扫描不能遗漏最后一年。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1109. 航班预订统计 | 中等 | 同样累计闭区间贡献，死亡当年仍计入，所以应在death+1处减去人数。 |
| 253. 会议室 II | 中等 | 同样求最大同时活跃数量，本题区间右端包含，会议常用半开区间，事件顺序与边界不同。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！