LeetCode 2055. 蜡烛之间的盘子

约 5 分钟
文章信息 2 个分类 4 个标签
分类
LeetCode 中等
标签
数组 字符串 二分查找 前缀和

题目描述

✅ 2055. 蜡烛之间的盘子

题意分析

字符串中的 * 表示盘子，| 表示蜡烛。每个查询给出闭区间 [l,r]，统计其中左右两边都能找到区间内蜡烛的盘子数。

盘子和充当边界的蜡烛都必须位于本次查询内，区间外蜡烛不能提供包围条件。蜡烛之间可以有更多蜡烛，只统计盘子；查询很多且字符串不变，适合预处理后重复使用。

解法：最近蜡烛位置与盘子前缀和

核心思路

[!blue]

先确定哪些盘子有资格计入。设 a 是从 l 向右找到的第一根蜡烛，b 是从 r 向左找到的最后一根蜡烛。位于 a 之前的盘子没有查询内左蜡烛，位于 b 之后的没有查询内右蜡烛，都不能计入；a、b 之间的每个盘子则都由这两根蜡烛包围。

因此找到查询内最左、最右两根蜡烛后，答案就是它们之间的盘子总数。若没有两根不同且有序的蜡烛，答案为零，不需要逐个盘子判断。

预处理 left[i] 为不超过 i 的最近蜡烛下标，right[i] 为不小于 i 的最近蜡烛下标，当前位置本身若是蜡烛就可以取自身，不存在时记 -1。一趟从左向右、一趟从右向左扫描，保存最近遇到的蜡烛即可建立两张表。

另令 prefix[i] 表示前 i 个字符中的盘子数。查询直接取 a = right[l]、b = left[r]。只有 a >= 0 且 a < b 时才有合法两端；由于 a >= l、b <= r，这个顺序条件同时保证它们都在查询区间内。

此时 prefix[b] - prefix[a] 统计 [a,b) 内的盘子。虽然包含左端下标 a，但那里是蜡烛、贡献为零，因此结果恰好等于严格夹在两根蜡烛之间的盘子数量。

解题步骤

  1. 从左向右构建盘子前缀和，同时记录每个位置左侧含自身的最近蜡烛。
  2. 从右向左记录每个位置右侧含自身的最近蜡烛，缺失统一记为 -1。
  3. 对每个查询，直接读取左端向右的蜡烛 a 和右端向左的蜡烛 b。
  4. a >= 0 且 a < b 时用前缀差计数，否则保留答案零。
  5. 按查询原顺序返回结果数组。

代码实现

class Solution {
    public int[] platesBetweenCandles(String s, int[][] queries) {
        int n = s.length();
        int candle = -1;
        int[] prefix = new int[n + 1];
        int[] left = new int[n];
        int[] right = new int[n];

        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + (s.charAt(i) == '*' ? 1 : 0);

            if (s.charAt(i) == '|') {
                candle = i;
            }

            left[i] = candle;
        }

        candle = -1;

        for (int i = n - 1; i >= 0; i--) {
            if (s.charAt(i) == '|') {
                candle = i;
            }

            right[i] = candle;
        }

        int[] answer = new int[queries.length];

        for (int i = 0; i < queries.length; i++) {
            int a = right[queries[i][0]];
            int b = left[queries[i][1]];

            if (a >= 0 && a < b) {
                answer[i] = prefix[b] - prefix[a];
            }
        }

        return answer;
    }
}

func platesBetweenCandles(s string, queries [][]int) []int {
    n := len(s)
    prefix, left, right := make([]int, n+1), make([]int, n), make([]int, n)
    candle := -1
    for i := 0; i < n; i++ {
        prefix[i+1] = prefix[i]
        if s[i] == '*' {
            prefix[i+1]++
        } else {
            candle = i
        }
        left[i] = candle
    }
    candle = -1
    for i := n - 1; i >= 0; i-- {
        if s[i] == '|' {
            candle = i
        }
        right[i] = candle
    }
    answer := make([]int, len(queries))
    for i, query := range queries {
        a, b := right[query[0]], left[query[1]]
        if a >= 0 && a < b {
            answer[i] = prefix[b] - prefix[a]
        }
    }
    return answer
}

复杂度分析

  • 时间复杂度：$O(n+q)$，其中 $n$ 为字符串长度，$q$ 为查询数。预处理线性完成，每次查询只做固定次数的读表和减法。
  • 空间复杂度：辅助空间为 $O(n)$，用于前缀和及两侧最近蜡烛；输出另占 $O(q)$。

关键点总结

[!green]

  • 查询先收缩到区间内最外侧的两根蜡烛，夹在其中的盘子才全部合法。
  • 最近位置表负责找边界，前缀和负责计数，两者解决不同的问题。
  • 表包含当前位置本身，查询端点是蜡烛时也能直接使用。
  • 前缀长度与字符下标要区分，边界蜡烛贡献为零使减法写法简化。

易错点总结

[!yellow]

  • 左边界应向右找蜡烛，右边界应向左找，方向反了可能用到区间外节点。
  • 前缀和只统计盘子，不能把总字符数当作盘子数。
  • 两端落到同一根蜡烛时也不合法，需要严格满足 a < b。
  • 缺失下标为 -1，判断合法后才能访问前缀数组。
  • 只有前缀和还不能直接返回查询区间的全部盘子，边缘没有被包住的盘子必须排除。

相似题目

题目 难度 关联与区别
303. 区域和检索 - 数组不可变 简单 复用静态前缀和查询；本题在做差之前，还要把区间边界收缩到合法蜡烛。
34. 在排序数组中查找元素的第一个和最后一个位置 中等 若只存蜡烛下标，可用两次边界二分找区间内首尾蜡烛；与预处理最近位置形成时间空间取舍。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/68035414
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！