LeetCode 821. 字符的最短距离

约 8 分钟
文章信息 7 个分类 3 个标签
分类
LeetCode CodeTop 简单 未解决 2-5 腾讯 百度
标签
数组 字符串 双指针
目录

题目描述

✅ 821. 字符的最短距离

题意分析

给一个字符串 s 和一个字符 c，题目保证 c 至少在 s 里出现一次。要为每个下标 i 算出它到最近的那个 c 的距离，距离定义为下标之差的绝对值。

「最近」意味着候选只有两个方向：i 左边离它最近的那个 c，和 i 右边离它最近的那个 c，答案是二者取小。中间隔着的其他 c 一律不可能更优。

s[i] == c 时距离为 0，这些位置是天然的基准点，也是两个方向搜索的起止依据。

约束上 n 最多 $10^4$，但仍值得写成线性；另外题目保证 c 存在，所以不必处理「一个都找不到」的无解分支，但代码里的哨兵初值仍要保证「没遇到过 c」时给出的候选距离大于任何真实距离。

解法：左右方向距离预处理

核心思路

暴力做法是对每个位置向左右两边逐格扩展，直到撞上第一个 c 就停。当 c 只出现在字符串的一端时，几乎每个位置都要扫过大半个串，最坏是 $O(n^2)$。

瓶颈在于相邻位置的搜索范围高度重叠：i 和 i + 1 向左看时走的是几乎相同的一段路，同一批字符被反复访问。

换个角度：从左往右扫的过程中，「到目前为止最后一个出现的 c 的下标」是个只增不减的量，可以边扫边顺手维护，完全不用回头。从右往左同理可以维护「后面第一个 c 的下标」。两个方向各得一个候选距离，取小即为答案。

正向扫描维持的不变量是：处理下标 i 之后，prev 恒等于区间 [0, i] 内最后一个 c 的下标；若这段里还没出现过 c，prev 保持哨兵值 -n，此时 i - prev = i + n \ge n，一定大于任何真实距离（真实距离上限是 n - 1），因而在后续取小时必被淘汰。反向扫描的不变量对称：prev 恒等于 [i, n - 1] 内第一个 c 的下标，哨兵取 2n，同样保证 prev - i \ge n + 1 大于所有真实距离。

解题步骤

  • 开长度 n 的答案数组 res，prev 置 -n，从左往右扫。哨兵之所以取 -n 而不是 -1 或 0，是因为它必须让「左边没有 c」这种情况算出的候选距离超过所有真实距离，否则会在取小时把假距离留下来。
  • 每步先判断 s[i] == c，是就把 prev 更新成 i。更新必须在写 res[i] 之前，这样当 i 自己就是 c 时能立刻得到距离 0。
  • 写 res[i] = i - prev。正向扫描里 prev 一定不大于 i，所以这个减法天然非负，不需要取绝对值。
  • 把 prev 重置为 2 * n，改从右往左扫。第二遍复用同一个 res 数组，省掉一个辅助数组。
  • 同样先更新 prev，再算 rightDist = prev - i，只有当它比 res[i] 小时才覆盖。这里必须取小而不是直接覆盖，否则左边算出的正确答案会被右边更差的候选冲掉。
  • 两遍扫完直接返回 res。

以 s = "loveleetcode"、c = 'e' 走一遍（n = 12，e 出现在下标 3、5、6、11）：

正向扫描，prev 初值 -12。下标 0 到 2 都没遇到 e，res 依次得到 0 + 12 = 12、13、14，全是被哨兵撑大的假值。下标 3 是 e，prev 更新为 3，res[3] = 0。下标 4 得 4 - 3 = 1。下标 5、6 都是 e，prev 依次更新，两处 res 都是 0。下标 7 到 10 依次得 1、2、3、4。下标 11 是 e，res[11] = 0。正向结果是 [12, 13, 14, 0, 1, 0, 0, 1, 2, 3, 4, 0]。

反向扫描，prev 重置为 24。下标 11 是 e，prev 更新为 11，右侧距离 0，res[11] 保持 0。下标 10 的右侧距离是 11 - 10 = 1，小于原值 4，覆盖为 1。下标 9 得 2，小于 3，覆盖为 2。下标 8 的右侧距离是 3，不小于原值 2，保留 2。下标 7 的右侧距离是 4，不小于原值 1，保留 1。下标 6、5 都是 e，prev 依次更新，两处仍是 0。下标 4 的右侧距离是 5 - 4 = 1，与原值 1 相等，保留 1。下标 3 是 e，保持 0。下标 2 的右侧距离 3 - 2 = 1 远小于哨兵留下的 14，覆盖为 1。下标 1 得 2，下标 0 得 3。

最终 res = [3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0]。挑一个位置核对：下标 8 左边最近的 e 在 6、距离 2，右边最近的在 11、距离 3，取小是 2，与结果一致。

代码实现

class Solution {
    // 只做左右一次线性扫描就能把两侧候选距离分别算出来，比从每个位置向两边扩展更高效。
    public int[] shortestToChar(String s, char c) {
        int n = s.length();
        int[] res = new int[n];

        int prev = -n;
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == c) {
                prev = i;
            }
            res[i] = i - prev;
        }

        prev = 2 * n;
        for (int i = n - 1; i >= 0; i--) {
            if (s.charAt(i) == c) {
                prev = i;
            }
            int rightDist = prev - i;
            if (rightDist < res[i]) {
                res[i] = rightDist;
            }
        }

        return res;
    }
}

func shortestToChar(s string, c byte) []int {
    // 只做左右一次线性扫描就能把两侧候选距离分别算出来，比从每个位置向两边扩展更高效。
    n := len(s)
    res := make([]int, n)

    prev := -n
    for i := 0; i < n; i++ {
        if s[i] == c {
            prev = i
        }
        res[i] = i - prev
    }

    prev = 2 * n
    for i := n - 1; i >= 0; i-- {
        if s[i] == c {
            prev = i
        }
        right := prev - i
        if right < res[i] {
            res[i] = right
        }
    }

    return res
}

复杂度分析

  • 时间复杂度：$O(n)$，正反各扫一遍，每个位置只做常数次比较、减法和赋值。
  • 空间复杂度：$O(1)$，除了必须返回的 res 数组之外，只用了 prev 一个整数，第二遍扫描原地覆写 res，没有额外辅助数组。

关键点总结

  • 「到最近的某类元素的距离」是双向扫描的招牌信号。左右两侧的最优解互不影响，各扫一遍再取小，就把 $O(n^2)$ 的逐点扩展压成两次线性遍历。
  • 单调量是免费的。正向扫描时「左边最近的 c」只会往右移，反向扫描时「右边最近的 c」只会往左移，顺手维护即可，不需要任何额外结构。
  • 哨兵值要按「必须被淘汰」来设计，而不是随手写个 -1。定量地想一遍「真实距离最大是多少」，再让哨兵算出的候选严格超过它，这个习惯能省掉一大类隐蔽 bug。
  • 第二遍扫描要写成取小而非覆盖。第一遍的结果是候选之一，不是待丢弃的中间量，这决定了两遍之间的数据流方向。
  • 面试视角：能主动指出「这本质是多源 BFS 在一维上的退化形态」，并顺势关联到 542 的二维版本，比只写出两次 for 循环更能说明你抓住了模型而不是背了模板。
  • 面试视角：把 res 数组复用于两遍扫描是很自然的常数空间优化，写完后补一句「不计返回值则是 $O(1)$ 额外空间」，可以避免面试官误以为你用了两个数组。

易错点总结

  • 错误写法：把正向哨兵写成 -1。用 s = "aab"、c = 'b' 试：res[0] 得到 0 - (-1) = 1，可下标 0 左边根本没有 b；反向扫描算出的真实距离是 2，取小后留下假值 1，正确答案是 2。
  • 错误写法：反向哨兵取 n 而不是 2 * n。用 s = "baaa"、c = 'b' 试：n = 4，下标 3 的反向候选是 4 - 3 = 1，但它右边一个 b 也没有，真实距离是 3，答案被压小。
  • 错误写法：只做一次扫描就返回。用 s = "loveleetcode"、c = 'e' 试：下标 0、1、2 左边没有 e，res 停在 12、13、14 这些哨兵撑出来的值上，必须靠反向扫描才能补正。
  • 错误写法：反向扫描时直接覆盖，写成 res[i] = prev - i。同一组用例里下标 8 左边距离 2、右边距离 3，覆盖后得到 3，正确答案是 2。
  • 错误写法：更新 prev 与写 res[i] 的顺序颠倒，先算距离再判断 s[i] == c。用 s = "ee" 试：下标 1 会拿上一轮的 prev = 0 算出距离 1，但 s[1] 自己就是 e，正确答案是 0。
  • 错误写法：两个方向都写成 prev - i（或都写成 i - prev）。正向扫描里 prev 不大于 i、反向扫描里 prev 不小于 i，写反的那一遍会得到负数，取小之后整列答案变成负值。
  • 错误写法：把哨兵改成 Integer.MIN_VALUE 图省事。i - Integer.MIN_VALUE 立刻整数溢出成负数，比任何真实距离都小，会在取小时把所有正确答案挤掉。
  • 错误写法：改用「先收集所有 c 的下标再对每个位置二分」的思路，却漏掉二分结果落在两端的情况。当 i 在首个 c 之前或末个 c 之后时，会去访问不存在的相邻候选而下标越界。

相似题目

题目 难度 考察点
42. 接雨水 困难 同样预处理左右两侧信息，但比的是最大值
542. 01 矩阵 中等 升到二维，需多源 BFS 或两遍动态规划
849. 到最近的人的最大距离 中等 求的是这些最近距离里的最大值，两端要特判
1162. 地图分析 中等 二维多源扩散，求最远的那个陆地距离
244. 最短单词距离 II 中等 需支持多次查询，得预存下标列表并双指针求解