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

2021-10-09 HGNULB 约 4 分钟

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

分类

LeetCode CodeTop 中等 未解决 1-2 虾皮

标签

数组

题目描述

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

题意分析

1 表示有人，0 表示空位。选择一个空位，使它与最近已有人的下标距离尽可能大，返回这个距离。题目保证至少有一个人和一个空位。

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

核心思路

[!blue]

同一段连续空位中的任意座位，最近的人只可能是紧邻这段的左边或右边的人，更远的人不需要考虑。因此可以把空位划成连续段，分别求出每段的最佳距离，再取最大值。

对中间空段，设长度为 len，两侧人的下标距离是 len + 1。坐在其中任何位置，到两边的距离之和都等于 len + 1，较小的一个不可能超过 floor((len + 1) / 2)；坐在中间位置就能达到这个上界，所以这就是该段的最优值。

贴着数组端点的空段只有一侧有人，越往外侧坐距离越大。选择最左端或最右端，最近距离正好等于空段长度 len，不能再除以 2。

扫描时用半开区间 [i, j) 表示一整段空位，长度为 j - i。i == 0 或 j == n 就是端点段，否则是中间段。每段计算后令 i = j，不再重新扫描已处理的空位。

解题步骤

1. 遇到有人座位就跳过。
2. 从空位起点向右找到整段结束位置。
3. 若空段贴着任一端点，候选距离取段长；否则取 (段长 + 1) / 2 的整数除法结果。
4. 更新全局最大距离并继续下一段。

代码实现

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)$，逐段扫描且不回退。
• 空间复杂度：$O(1)$。

关键点总结

[!green]

• 端点段与中间段受到的两侧约束不同。
• 空段长度和两个人的下标差相差一。
• 答案是最近距离的最大值，不是座位下标。

易错点总结

[!yellow]

• 端点空段也除以二：低估靠最外侧的位置。
• 中间段直接用 len/2：空位段长比两侧人的距离少 1，会低估部分奇数长度空段的答案。
• 遗漏右端空段：最后一个人之后也可能有最佳空位。
• 探测段末不判断数组边界：末尾连续空位会导致越界。

相似题目

题目	难度	关联与区别
475. 供暖器	中等	同样取到最近已有位置的距离，原题保证每所房子被供暖，本题在空位中选择最远离已坐人的位置。
821. 字符的最短距离	简单	原题返回所有位置到目标的最短距离，本题只在空位中取这些距离的最大值。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2021/69057955

许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！