2055. 蜡烛之间的盘子 : 二分 & 前缀和运用题-一一网

Offer 驾到，掘友接招！我正在参与2022春招打卡活动，点击查看活动详情。

题目描述

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

Tag : 「前缀和」、「二分」

给你一个长桌子，桌子上盘子和蜡烛排成一列。给你一个下标从 $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]$ 内的盘子数量」操作可直接查询「前缀和」数组。

代码：

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;
    }
}
复制代码

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

前缀和

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

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

代码：

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;
    }
}
复制代码