LC 2055. 蜡烛之间的盘子

题目描述

这是 LeetCode 上的 2055. 蜡烛之间的盘子 ，难度为中等。

给你一个长桌子，桌子上盘子和蜡烛排成一列。给你一个下标从 $0$ 开始的字符串 s ，它只包含字符 '*' 和 '|' ，其中 '*' 表示一个盘子，'|' 表示一支蜡烛。

同时给你一个下标从 $0$ 开始的二维整数数组 queries ，其中 $queries[i] = [lefti, righti]$ 表示子字符串 $s[left_i…right_i]$ （包含左右端点的字符）。对于每个查询，你需要找到子字符串中在两支蜡烛之间的盘子的数目。如果一个盘子在子字符串中左边和右边都至少有一支蜡烛，那么这个盘子满足在两支蜡烛之间。

比方说，s = "||**||**|*" ，查询 $[3, 8]$ ，表示的是子字符串 "*||**|" 。子字符串中在两支蜡烛之间的盘子数目为 $2$ ，子字符串中右边两个盘子在它们左边和右边都至少有一支蜡烛。
请你返回一个整数数组 $answer$ ，其中 $answer[i]$ 是第 $i$ 个查询的答案。

示例 1:

输入：s = "**|**|***|", queries = [[2,5],[5,9]]

输出：[2,3]

解释：
- queries[0] 有两个盘子在蜡烛之间。
- queries[1] 有三个盘子在蜡烛之间。

示例 2:

输入：s = "***|**|*****|**||**|*", queries = [[1,17],[4,5],[14,17],[5,11],[15,16]]

输出：[9,0,0,0,0]

解释：
- queries[0] 有 9 个盘子在蜡烛之间。
- 另一个查询没有盘子在蜡烛之间。

提示：

$3 <= s.length <= 10^5$
s 只包含字符 '*' 和 '|' 。
$1 <= queries.length <= 10^5$
$queries[i].length == 2$
$0 <= lefti <= righti < s.length$

二分 + 前缀和

对于任意一个查询 $[a, b]$ 而言，我们需要统计所有左边和右边能够找到蜡烛的盘子数量。

一个自然的想法是：找到区间 $[a, b]$ 两边缘的蜡烛，分别记为 $c$ 和 $d$，显然区间 $[c, d]$ 内的盘子都是需要被统计的。

因此，我们可以对字符串 s 进行从前往后的扫描，将所有的蜡烛下标添加到数组（数组严格递增），并预处理出盘子的「前缀和」数组。

然后处理询问时的「找区间 $[a, b]$ 边缘蜡烛」操作可通过对数组「二分」来做，而「查询区间 $[c, d]$ 内的盘子数量」操作可直接查询「前缀和」数组。

Java 代码：

class Solution {
    public int[] platesBetweenCandles(String s, int[][] qs) {
        char[] cs = s.toCharArray();
        int n = cs.length, m = qs.length;
        int[] ans = new int[m], sum = new int[n + 1];
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (cs[i] == '|') list.add(i);
            sum[i + 1] = sum[i] + (cs[i] == '*' ? 1 : 0);
        }
        if (list.size() == 0) return ans;
        for (int i = 0; i < m; i++) {
            int a = qs[i][0], b = qs[i][1];
            int c = -1, d = -1;
            // 找到 a 右边最近的蜡烛
            int l = 0, r = list.size() - 1;
            while (l < r) {
                int mid = l + r >> 1;
                if (list.get(mid) >= a) r = mid;
                else l = mid + 1;
            }
            if (list.get(r) >= a) c = list.get(r);
            else continue;
            // 找到 b 左边最近的蜡烛
            l = 0; r = list.size() - 1;
            while (l < r) {
                int mid = l + r + 1 >> 1;
                if (list.get(mid) <= b) l = mid;
                else r = mid - 1;
            }
            if (list.get(r) <= b) d = list.get(r);
            else continue;
            if (c <= d) ans[i] = sum[d + 1] - sum[c];
        }
        return ans;
    }
}

C++ 代码：

class Solution {
public:
    vector<int> platesBetweenCandles(string s, vector<vector<int>>& qs) {
        vector<int> ans(qs.size(), 0);
        vector<int> sum(s.length() + 1, 0);
        vector<int> list;
        for (int i = 0; i < s.length(); i++) {
            if (s[i] == '|') list.push_back(i);
            sum[i + 1] = sum[i] + (s[i] == '*' ? 1 : 0);
        }
        if (list.empty()) return ans;
        for (int i = 0; i < qs.size(); i++) {
            int a = qs[i][0], b = qs[i][1];
            int c = -1, d = -1;
            // 找到 a 右边最近的蜡烛
            int l = 0, r = list.size() - 1;
            while (l < r) {
                int mid = l + r >> 1;
                if (list[mid] >= a) r = mid;
                else l = mid + 1;
            }
            if (list[r] >= a) c = list[r];
            else continue;
            // 找到 b 左边最近的蜡烛
            l = 0; r = list.size() - 1;
            while (l < r) {
                int mid = l + r + 1 >> 1;
                if (list[mid] <= b) l = mid;
                else r = mid - 1;
            }
            if (list[r] <= b) d = list[r];
            else continue;
            if (c <= d) ans[i] = sum[d + 1] - sum[c];
        }
        return ans;
    }
};

Python 代码：

class Solution:
    def platesBetweenCandles(self, s: str, qs: List[List[int]]) -> List[int]:
        ans = [0] * len(qs)
        sum_val = [0] * (len(s) + 1)
        candle_positions = [i for i, char in enumerate(s) if char == '|']
        for i in range(len(s)):
            sum_val[i + 1] = sum_val[i] + (s[i] == '*')
        if not candle_positions:
            return ans
        for i in range(len(qs)):
            a, b = qs[i]
            c, d = -1, -1
            # 找到 a 右边最近的蜡烛
            l, r = 0, len(candle_positions) - 1
            while l < r:
                mid = l + r >> 1
                if candle_positions[mid] >= a:
                    r = mid
                else:
                    l = mid + 1
            if candle_positions[r] >= a:
                c = candle_positions[r]
            else:
                continue
            # 找到 b 左边最近的蜡烛
            l, r = 0, len(candle_positions) - 1
            while l < r:
                mid = l + r + 1 >> 1
                if candle_positions[mid] <= b:
                    l = mid
                else:
                    r = mid - 1
            if candle_positions[r] <= b:
                d = candle_positions[r]
            else:
                continue
            if c <= d:
                ans[i] = sum_val[d + 1] - sum_val[c]
        return ans

TypeScript 代码：

function platesBetweenCandles(s: string, qs: number[][]): number[] {
    const ans = new Array(qs.length).fill(0);
    const sum = new Array(s.length + 1).fill(0);
    const list = [];
    for (let i = 0; i < s.length; i++) {
        if (s[i] == '|') list.push(i);
        sum[i + 1] = sum[i] + (s[i] === '*' ? 1 : 0);
    }
    if (list.length == 0) return ans;
    for (let i = 0; i < qs.length; i++) {
        const a = qs[i][0], b = qs[i][1];
        let c = -1, d = -1;
        // 找到 a 右边最近的蜡烛
        let l = 0, r = list.length - 1;
        while (l < r) {
            const mid = l + r >> 1;
            if (list[mid] >= a) r = mid;
            else l = mid + 1;
        }
        if (list[r] >= a) c = list[r];
        else continue;
        // 找到 b 左边最近的蜡烛
        l = 0; r = list.length - 1;
        while (l < r) {
            const mid = l + r + 1 >> 1;
            if (list[mid] <= b) l = mid;
            else r = mid - 1;
        }
        if (list[r] <= b) d = list[r];
        else continue;
        if (c <= d) ans[i] = sum[d + 1] - sum[c];
    }
    return ans; 
};

时间复杂度：令 s 的长度为 $n$，qs 长度为 $m$。统计所有的蜡烛并存入 list 的复杂度为 $O(n)$；预处理前缀和数组复杂度为 $O(n)$；处理单个询问需要进行两次二分（蜡烛数量最多为 $n$），复杂度为 $O(\log{n})$，共有 $m$ 个询问需要处理，复杂度为 $O(m \times \log{n})$。整体复杂度为 $O(n + m\log{n})$
空间复杂度：$O(n)$

前缀和

更进一步，在给定 s 的前提下，每个位置其左边和右边最近的蜡烛唯一确定。

我们可以在预处理前缀和的同时，预处理每个位置左右最近的蜡烛下标，从而省去每次二分。

Java 代码：

class Solution {
    public int[] platesBetweenCandles(String s, int[][] qs) {
        char[] cs = s.toCharArray();
        int n = cs.length, m = qs.length;
        int[] l = new int[n], r = new int[n];
        int[] sum = new int[n + 1];
        for (int i = 0, j = n - 1, p = -1, q = -1; i < n; i++, j--) {
            if (cs[i] == '|') p = i;
            if (cs[j] == '|') q = j;
            l[i] = p; r[j] = q;
            sum[i + 1] = sum[i] + (cs[i] == '*' ? 1 : 0);
        }
        int[] ans = new int[m];
        for (int i = 0; i < m; i++) {
            int a = qs[i][0], b = qs[i][1];
            int c = r[a], d = l[b];
            if (c != -1 && c <= d) ans[i] = sum[d + 1] - sum[c];
        }
        return ans;
    }
}

C++ 代码：

class Solution {
public:
    vector<int> platesBetweenCandles(string s, vector<vector<int>>& qs) {
        vector<int> l(s.length(), 0), r(s.length(), 0);
        vector<int> sum(s.length() + 1, 0);
        for (int i = 0, j = s.length() - 1, p = -1, q = -1; i < s.length(); i++, j--) {
            if (s[i] == '|') p = i;
            if (s[j] == '|') q = j;
            l[i] = p; r[j] = q;
            sum[i + 1] = sum[i] + (s[i] == '*' ? 1 : 0);
        }
        vector<int> ans(qs.size(), 0);
        for (int i = 0; i < qs.size(); i++) {
            int a = qs[i][0], b = qs[i][1];
            int c = r[a], d = l[b];
            if (c != -1 && c <= d) ans[i] = sum[d + 1] - sum[c];
        }
        return ans;
    }
};

时间复杂度：$O(n + m)$
空间复杂度：$O(n)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.2055 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

二分前缀和

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

LC 798. 得分最高的最小轮调上一篇

LC 504. 七进制数下一篇