LeetCode 849. 到最近的人的最大距离

2021-10-09 HGNULB 约 9 分钟

文章信息 6 个分类 1 个标签

分类

题目描述

✅ 849. 到最近的人的最大距离

题意分析

一排座位用 0/1 数组给出，1 表示已有人、0 表示空位。要在某个空位坐下，使得「自己到最近的那个人的距离」尽可能大，返回这个最大值。距离按下标差计算。

题目保证至少有一个 1、也至少有一个 0，所以答案一定存在且至少为 1，不需要考虑无解。

关键在于目标函数的形状：坐下之后，到最近的人的距离只取决于左边最近的 1 和右边最近的 1，与更远的人无关。这意味着整排座位可以按 1 的位置切成若干互不影响的空位段，每段单独求最优，再取全局最大。这是一个「局部可分解」的信号——一次线性扫描就够，不需要任何数据结构。

段的类型必须分开讨论，这是全题唯一的难点。夹在两个 1 之间的空位段，坐在正中间时左右距离最平衡；而贴着数组左端或右端的空位段，一侧根本没有人，可以一路坐到最边上，距离等于整段长度。把这两类混为一谈是本题最主要的失分点。

约束里 $n$ 最大 2 万，$O(n)$ 绰绰有余；数组元素只有 0 和 1，不需要排序也不需要哈希。

边界要盯住：[1,0,0,0] 这种右端开口的情况答案是 3；[0,0,1] 这种左端开口的答案是 2；[1,0,1] 中间段长度为 1，答案是 1；[0,1,0] 两端各有一个长度为 1 的开口段，答案也是 1。

解法：一次扫描统计 0 段长度

核心思路

暴力做法是对每个空位分别向左向右各扫一遍，找最近的 1，取两者较小值，再对所有空位取最大。这个做法完全正确，但每个空位最坏要扫 $O(n)$，总共 $O(n^2)$，在 2 万规模下就有 4 亿次操作，明显浪费。

瓶颈在于同一段空位里的每个位置，重复地在扫描同一对邻居。既然一段连续 0 的左右边界（那两个 1）对段内所有位置都是同一对，那就没必要逐个位置去找，直接对整段一次性算出最优答案。

由此得到分段的观察：把数组按 1 切开，每一段连续的 0 属于以下三类之一。设这一段占据下标区间 [i, j)，长度 len = j - i。

第一类，左端开口段（i == 0）：左边没有任何人，坐在下标 0 处，最近的人是 seats[j]，距离为 j - 0 = len。

第二类，右端开口段（j == n）：右边没有任何人，坐在下标 n - 1 处，最近的人是 seats[i-1]，距离为 (n-1) - (i-1) = len。

第三类，中间夹段（i > 0 且 j < n）：两侧下标 i-1 与 j 处都有人，两人相隔 j - (i-1) = len + 1。坐在正中间时，到两侧的距离分别是 $\lfloor \frac{len+1}{2} \rfloor$ 和 $\lceil \frac{len+1}{2} \rceil$，取较小者即 $\lfloor \frac{len+1}{2} \rfloor$，写成整数运算就是 (len + 1) / 2。

不变量：外层循环每次迭代开始时，i 指向一个尚未处理的下标，且 answer 已经等于「下标小于 i 的所有空位中，到最近的人的距离的最大值」。每处理完一段 0（或跳过一个 1），不变量继续成立。扫描结束时 i == n，answer 即为全局答案。

注意「两个开口段可以并存」：[0,0,1,0,0,0] 的左段长 2、右段长 3，都按 len 算，答案是 3。也要注意开口段的判定用的是下标位置而不是「这段前面有没有 1」的记忆变量，写起来更不容易错。

解题步骤

初始化 answer = 0、i = 0：answer 取 0 作初值是安全的，因为题目保证至少有一个空位，任何一段都会给出至少 1 的候选值，0 不会成为最终答案。

遇到 1 就跳过：seats[i] == 1 时 i++ 并 continue。有人的位置不能坐，也不构成段，直接略过。

用 j 探出整段 0 的右边界：从 j = i 出发，只要 j < n && seats[j] == 0 就 j++。循环结束时 j 要么等于 n，要么指向段右侧第一个 1。用左闭右开区间 [i, j) 表示这一段，长度直接是 j - i，避免了加一减一的混乱。

判段型并更新答案：i == 0 || j == n 说明这段贴着数组的某一端，候选值取 len；否则是中间夹段，候选值取 (len + 1) / 2。用「或」是因为一段既可能贴左端也可能贴右端（整排只有一段 0 时两者同时成立），任一成立就按开口段算。

推进 i = j：直接跳到段末，保证每个下标只被外层访问一次，总复杂度线性。这里绝不能写成 i++，那样会对同一段重复计算 len 次。

返回 answer。

以 seats = [1,0,0,0,1,0,1] 走一遍，n = 7。

i = 0：seats[0] = 1，跳过，i = 1。

i = 1：seats[1] = 0，探边界，j 从 1 走到 4（seats[4] = 1 停下）。len = 4 - 1 = 3。i = 1 != 0 且 j = 4 != 7，是中间夹段，候选 (3 + 1) / 2 = 2。answer 由 0 更新为 2。含义是：左右两人在下标 0 和 4，相隔 4，坐在下标 2 时左右各距 2。i = 4。

i = 4：seats[4] = 1，跳过，i = 5。

i = 5：seats[5] = 0，j 从 5 走到 6（seats[6] = 1 停下）。len = 1。中间夹段，候选 (1 + 1) / 2 = 1，不大于 2，answer 保持 2。i = 6。

i = 6：seats[6] = 1，跳过，i = 7 == n，循环结束，返回 2。

再看开口段的用例 seats = [1,0,0,0]：i = 1 时 j 一路走到 4 即 n，len = 3，因为 j == n 走开口分支，候选 3，答案为 3——坐在最右端下标 3，最近的人在下标 0，距离正是 3。如果这里误用中间段公式会得到 (3+1)/2 = 2，直接答错。

代码实现

class Solution {
    public int maxDistToClosest(int[] seats) {
        int n = seats.length;
        int answer = 0;
        int i = 0;
        while (i < n) {
            if (seats[i] == 1) {
                i++;
                continue;
            }
            int j = i;
            while (j < n && seats[j] == 0) {
                j++;
            }
            int len = j - i;
            if (i == 0 || j == n) {
                answer = Math.max(answer, len);
            } else {
                answer = Math.max(answer, (len + 1) / 2);
            }
            i = j;
        }
        return answer;
    }
}

func maxDistToClosest(seats []int) int {
    n := len(seats)
    answer := 0
    i := 0
    for i < n {
        if seats[i] == 1 {
            i++
            continue
        }
        j := i
        for j < n && seats[j] == 0 {
            j++
        }
        length := j - i
        if i == 0 || j == n {
            if length > answer {
                answer = length
            }
        } else {
            cand := (length + 1) / 2
            if cand > answer {
                answer = cand
            }
        }
        i = j
    }
    return answer
}

复杂度分析

时间复杂度：$O(n)$。内层探边界的 j 与外层的 i 合起来只在数组上单调右移一遍，i = j 的跳跃保证没有任何下标被访问两次。

空间复杂度：$O(1)$。只用了 answer、i、j、len 四个整数，不开任何辅助数组，也没有递归。

关键点总结

目标只依赖左右最近的两个人，说明问题可按 1 的位置切成互不影响的段——识别出「可分解」结构，就能把 $O(n^2)$ 的逐点扫描降成 $O(n)$ 的逐段计算。

端点段与中间段的公式不同（len 对 (len+1)/2），根源是端点段只有一侧有约束。凡是「距离/覆盖」类题目，都要先问一句「边界处是不是少了一侧约束」。

用左闭右开区间 [i, j) 描述段，长度直接是 j - i，段型判定直接是 i == 0 与 j == n，比维护「上一个 1 的位置」少一半的加减一错误。

中间段的 (len + 1) / 2 本质是「两人间距 len + 1 的一半向下取整」，写成 (len + 1) / 2 而不是 len / 2 + 1 之类，才能在 len 为偶数时正确。

扫完一段后必须 i = j 而不是 i++，这是把线性算法写成平方算法的常见分水岭。

面试视角：主动说出「答案候选只有三类段」并给出每类的闭式解，比写完代码再解释更有说服力；面试官往往会追问「为什么端点段是 len 而不是 len - 1」，答案是可以坐到下标 0 或 n-1。

易错点总结

端点段套用中间段公式：[1,0,0,0] 会算出 (3+1)/2 = 2，正确答案是 3。这是本题第一大错误。

中间段写成 len / 2：[1,0,1] 中 len = 1，1/2 = 0，返回 0，而正确答案是 1（坐在下标 1，左右各距 1）。

中间段写成 (len + 1) / 2 之外的取整方向：写成 (len + 2) / 2，[1,0,0,1] 会得到 2，但实际坐在下标 1 或 2 时最近距离都只有 1，答案被高估。

段型判定只判 i == 0 漏掉 j == n：[1,0,0,0] 中 i = 1 != 0，会走中间分支得到 2，右端开口被当成夹段。

推进写成 i++ 而不是 i = j：[1,0,0,0,0,0,1] 这类长段会对同一段重复计算，答案虽然仍对（取的是最大值），但复杂度退化到 $O(n^2)$，n = 20000 且大段全 0 时超时。

探边界循环忘记 j < n 的越界保护：[1,0,0] 中 j 会一直走到 3 并访问 seats[3]，直接数组越界异常。

answer 初值设成 Integer.MAX_VALUE 或用 min 更新：本题求最大值，初值应为 0 并用 max 更新；用 min 会在 [1,0,0,0,1,0,1] 上返回 1 而不是 2。

把「距离」理解成中间空位的个数：[1,0,1] 会算成 1 个空位即距离 1（巧合正确），但 [1,0,0,0] 会算成 3 个空位对 3（也巧合正确）；真正暴露问题的是 [1,0,0,1]，按空位数会得到 2，而下标差最大只有 1。

误以为要返回最优座位的下标：题目要的是最大距离这个数值，返回下标会全部答错。

试图先把所有 1 的下标收集到列表再两两求差：思路可行但要额外处理首尾两个「虚拟边界」，漏掉其中一个就会在 [0,0,1] 或 [1,0,0] 上答错，且多花 $O(n)$ 空间，不如原地分段扫描。

相似题目

题目	难度	考察点
605. 种花问题	简单	同样按 0 段分类计数，端点段能多种一朵，公式随段型变化
485. 最大连续 1 的个数	简单	只需求最长 1 段长度，不区分段型，是本题分段扫描的最简形态
487. 最大连续1的个数 II	中等	允许翻转一个 0，需要记住前一段长度或改用滑动窗口
1004. 最大连续1的个数 III	中等	翻转次数推广到 k 次，标准可变长滑动窗口，与分段思路分道扬镳
1493. 删掉一个元素以后全为 1 的最长子数组	中等	必须删一个元素，答案要减一，边界处理与本题端点段的讨论同源
1552. 两球之间的磁力	中等	同样最大化「最小距离」，但位置可选且要放多个球，改用二分答案
424. 替换后的最长重复字符	中等	段的概念升级为窗口内众数，考察窗口收缩条件而非闭式公式