LeetCode 面试题 16.10. 生存人数

2021-09-13 HGNULB 约 10 分钟

文章信息 7 个分类 2 个标签

分类

LeetCode CodeTop 中等未解决 1-2 快手程序员面试金典（第 6 版）

题目描述

✅ 面试题 16.10. 生存人数

题意分析

给定两个等长数组 birth 和 death，第 i 个人出生于 birth[i] 年、死于 death[i] 年。要求找出存活人数最多的那一年；若有多个年份人数相同，返回其中最小的年份。

约束里有三个必须读出来的信号。第一，年份被限定在 1900 到 2000 之间，只有 101 个取值——这是在明示可以开一个定长数组按年份直接建索引，不需要离散化，也不需要排序。第二，题目明确规定"死亡当年仍然算存活"，也就是每个人的存活区间是闭区间 [birth[i], death[i]]，这一条直接决定了区间右端的处理方式。第三，要返回最小年份，意味着扫描时必须从小到大、且只在严格大于当前最大值时才更新答案。

边界上要覆盖：birth[i] == death[i]（当年出生当年去世，仍要计入这一年）；death[i] == 2000（右端顶到统计区间的上界）；birth[i] == 1900（左端顶到下界）；以及所有人的区间完全不相交时，答案应是最早那个人的出生年。

解法：差分数组 + 前缀和

核心思路

暴力做法是二重循环：对 1900 到 2000 的每一年，扫一遍所有人判断是否存活，取最大值。复杂度 $O(101n)$，在本题数据规模下其实能过，但瓶颈在于同一个人的区间被反复检查了上百次——一个活了 50 年的人，会在 50 个年份里各被判定一次，做的全是重复劳动。

关键观察是：我们并不需要知道"某一年有哪些人活着"，只需要知道"某一年活着的人数"。而人数这个量在时间轴上的变化极其稀疏——它只在有人出生时 +1、有人去世的次年 -1，其余年份保持不变。一个跨度 50 年的区间，对时间轴的影响只有两个端点，中间 48 年都是"继承上一年"。

这就引出差分数组：用 diff[y] 记录"第 y 年相对第 y-1 年的人数变化量"。给一个人区间 [b, d] 加一，等价于 diff[b] += 1 和 diff[d+1] -= 1——把 $O(区间长度)$ 的更新压缩成 $O(1)$ 的两次端点修改。所有人都处理完之后，对 diff 求前缀和，第 y 项的前缀和恰好就是第 y 年的存活人数。

不变量写清楚就是：设 $alive(y) = \sum_{t \le y} diff[t]$，则对任意年份 y，$alive(y)$ 恒等于"区间 $[b_i, d_i]$ 覆盖 y 的人数"。这一点可以逐人验证：某人贡献了 +1 在 b 处、-1 在 d+1 处，那么 y < b 时两项都未被累加、贡献 0；b <= y <= d 时只累加了 +1、贡献 1；y > d 时两项都被累加、贡献 0。正是我们要的闭区间语义。

因为要求最小年份，前缀和阶段从 1900 向 2000 单调扫描，并且只在 alive > bestAlive 时才更新答案。用严格大于是关键：相等时不更新，就保证了记录下来的永远是第一次达到该人数的年份，也就是最小的那个。

解题步骤

开一个长度 102 的差分数组 diff，下标 i 对应年份 1900 + i。长度取 102 而不是 101，是为了给 d + 1 可能达到的 2001 留一格（下标 101），避免右端点的减法越界。年份统一减去 1900 做偏移，是"值域已知且很小"时的标准建索引方式。

遍历每个人，做 diff[birth[i] - 1900]++。出生那年人数增加，这是区间左端点的贡献，必须落在 birth[i] 本身而不是它的前一年或后一年。

做 diff[death[i] + 1 - 1900]--，并用 death[i] + 1 <= 2000 做一次保护。减法落在 death[i] + 1 而不是 death[i]，正是因为"死亡当年仍算存活"——要让减法从死后第一年才开始生效。那句保护判断表示：若某人活到 2000 年，他的减法落在统计区间之外，对答案毫无影响，可以直接跳过。

从下标 0 到 100 做前缀累加，边累加边更新答案。alive += diff[i] 之后，alive 就是 1900 + i 这一年的存活人数。累加和判断必须在同一轮里完成，不需要额外开一个前缀和数组——这是滚动变量替代数组的常规优化。

更新条件写 alive > bestAlive。严格大于让"第一次达到峰值的年份"被保留下来，后面出现相同人数时不覆盖，从而满足"返回最小年份"。bestYear 初始化为 1900、bestAlive 初始化为 0，保证任何非空输入都会至少触发一次更新。

以 birth = [1900, 1901, 1950]、death = [1948, 1951, 2000] 走一遍：

建差分：第 1 人 [1900, 1948]，diff[0]++、diff[1949 - 1900] = diff[49]--。第 2 人 [1901, 1951]，diff[1]++、diff[52]--。第 3 人 [1950, 2000]，diff[50]++；死亡年是 2000，death + 1 = 2001 > 2000，减法被跳过。

前缀扫描：i = 0（1900 年），alive = 0 + 1 = 1，1 > 0 成立，记 bestAlive = 1、bestYear = 1900。i = 1（1901 年），alive = 1 + 1 = 2，2 > 1 成立，记 bestAlive = 2、bestYear = 1901。i = 2..48，diff 全为 0，alive 保持 2，2 > 2 不成立，答案不更新——这一步正是"严格大于"发挥作用的地方，若写成 >=，bestYear 会被一路刷到 1948。

i = 49（1949 年），alive = 2 - 1 = 1，不更新。i = 50（1950 年），alive = 1 + 1 = 2，2 > 2 不成立，仍不更新。i = 51，alive 保持 2。i = 52（1952 年），alive = 2 - 1 = 1。此后到 i = 100，alive 保持 1。

最终返回 bestYear = 1901。人工核对：1900 年只有第 1 人活着（1 人）；1901 到 1948 年第 1、2 人都活着（2 人）；1949 年只剩第 2 人；1950、1951 年第 2、3 人都活着（2 人）；此后只剩第 3 人。峰值是 2 人，最早出现在 1901 年，答案正确。

顺带验证闭区间：第 1 人死于 1948，减法落在下标 49（1949 年），所以 1948 年他仍被计入——若把减法写在 death[i] - 1900，1948 年就会少算一人，alive 在 i = 48 处提前掉到 1。

代码实现

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)$，其中 n 是人数、Y = 101 是年份跨度。建差分数组时每个人只做常数次端点修改（与他活了多少年无关），前缀扫描固定走 101 步。相比暴力的 $O(nY)$，把"区间长度"这个因子彻底消掉了。

空间复杂度：$O(Y)$，即 $O(1)$ 的常数级——差分数组固定 102 个整数，与人数 n 无关；前缀和用滚动变量 alive 代替数组，没有额外开销。

关键点总结

"给区间整体加一、最后求某点的值"就是差分数组的标准场景。把 $O(len)$ 的区间更新压成两次端点修改，最后一次前缀和还原全部结果；只要更新全部发生在查询之前，这个套路就成立（若更新与查询交错，则要升级成树状数组或线段树）。

闭区间和开区间的差别全在那个 +1 上。"死亡当年仍存活"意味着减法落在 d + 1；如果题目改成"死亡当年不算"，减法就落在 d。写差分前先把区间的开闭问句问清楚，这一个偏移量决定了整题的对错。

值域小且已知时，直接开定长数组建索引。年份 1900–2000 只有 101 个取值，减去基准值就是下标，完全不需要排序或离散化；值域大或稀疏时才需要把端点排序后做扫描线。

要"最早/最小的最优解"，就单调扫描 + 严格大于。相等时不更新，天然保留第一次达到峰值的位置。反过来要"最晚"就改成 >=。这一个符号是同类题的高频失分点。

面试视角：先给差分解法，再主动对比扫描线。面试官常追问"如果年份范围是 $10^9$ 呢"——那时定长数组开不下，要把所有 (birth, +1) 和 (death+1, -1) 事件收集起来排序，再顺序扫描，复杂度变成 $O(n \log n)$。能主动说出"值域小用差分数组、值域大用排序扫描线"这条选择标准，说明你掌握的是模型而不是模板。

易错点总结

错误写法：diff[death[i] - 1900]--（减法落在死亡当年） → 用例 birth = [1900]、death = [1900]：diff[0] 先加一又减一，alive 全程为 0，bestAlive 从未被更新，返回初始值 1900 虽然凑巧正确，但换成 birth = [1900, 1905]、death = [1900, 1910] 时，1900 年的存活人数被算成 0，答案错误地变成 1905。死亡当年仍算存活，减法必须落在次年。

错误写法：更新条件写成 alive >= bestAlive → 用例 birth = [1900, 1901]、death = [1948, 1951]：1901 到 1948 年人数都是 2，用 >= 会一路把 bestYear 刷到 1948，正确答案是 1901。

错误写法：差分数组长度开成 101 → 用例 birth = [1900]、death = [1999]：减法下标是 2000 - 1900 = 100，恰好是最后一格没问题；但若去掉 death[i] + 1 <= 2000 的保护、且有人活到 2000 年，下标 101 就越界抛异常。长度 102 加上那句保护是双保险。

错误写法：忘记减基准 1900，直接写 diff[birth[i]]++ → 用例 birth = [1900]：下标 1900 远超数组长度，直接越界。值域偏移是定长计数数组的必备步骤。

错误写法：前缀扫描的上界写成 i < 100 → 用例：峰值恰好出现在 2000 年（如所有人都在 2000 年前后出生）：最后一年没被检查，答案偏小。年份 1900..2000 对应下标 0..100，共 101 个，循环必须写 i <= 100 或 i < 101。

错误写法：bestAlive 初始化为 Integer.MAX_VALUE 或 -1 之外的值 → 若初始化成一个大数，任何真实人数都不满足"严格大于"，bestYear 停在初始的 1900；用例 birth = [1950]、death = [1960] 会返回 1900，正确答案是 1950。求最大值的初始值必须取到不可能超过的下界（这里是 0）。

错误写法：bestYear 初始化为 0 → 用例：所有人都在同一年出生死亡，且该年人数为 0 的情况不存在，所以通常会被更新；但若输入为空数组，返回 0 而不是合法年份。初始化成区间左端 1900 更安全。

错误写法：先把 diff 累加成一个完整的前缀和数组，再用 Arrays.stream(...).max() 找最大值，最后反查下标 → 用例 birth = [1900, 1901]、death = [1948, 1951]：max 只给出人数不给年份，反查时若用 indexOf 找第一个匹配值恰好正确，但多写了一遍扫描；更常见的错误是反查时找到的是最后一个匹配位置，返回 1948。一次扫描里同时维护最大值和位置更简洁也更不容易错。

错误写法：把区间加法写成循环 for (int y = birth[i]; y <= death[i]; y++) cnt[y - 1900]++; → 用例 n = 10^4、每人跨度 100 年：退化成 $O(nY)$，本题数据下能过，但完全放弃了差分这个考点；面试里会被直接要求改写。

错误写法：Go 里 diff := make([]int, 102) 写成 var diff []int → 用例任意输入：向长度为 0 的 nil 切片按下标赋值直接 panic。Go 的切片必须先 make 出长度才能按下标写入。

错误写法：把 alive 声明在内层循环里 → 用例任意输入：每年都从 0 重新累加，前缀和失去"继承上一年"的语义，alive 变成 diff[i] 本身，答案完全错乱。滚动变量必须声明在循环之外。

相似题目

题目	难度	考察点
1109. 航班预订统计	中等	最纯粹的差分模板题，区间加的是任意值而非固定的 1
1094. 拼车	中等	差分求每站载客数后还要与容量比较，是本题的"带阈值"版本
370. 区间加法	中等	只求最终数组而不求峰值，用来单独练差分与前缀和的对应关系
253. 会议室 II	中等	值域大到无法开数组，必须把端点排序后做扫描线或用最小堆
729. 我的日程安排表 I	中等	更新与查询交错进行，差分失效，要改用有序集合动态维护区间
1732. 找到最高海拔	简单	输入直接给的就是差分数组，只需前缀和取峰值，可作为反向练习