题目描述
这是 LeetCode 上的 2055. 蜡烛之间的盘子 ，难度为 中等。
Tag : 「前缀和」、「二分」
给你一个长桌子，桌子上盘子和蜡烛排成一列。给你一个下标从 00 开始的字符串 s ，它只包含字符 '*' 和 '|' ，其中 '*' 表示一个 盘子 ，'|' 表示一支 蜡烛 。
同时给你一个下标从 00 开始的二维整数数组 queries ，其中 queries[i] = [lefti, righti]queries[i]=[lefti,righti] 表示 子字符串 s[left_i...right_i]s[lefti...righti] （包含左右端点的字符）。对于每个查询，你需要找到 子字符串中 在 两支蜡烛之间 的盘子的 数目 。如果一个盘子在 子字符串中 左边和右边 都 至少有一支蜡烛，那么这个盘子满足在 两支蜡烛之间 。
比方说，s = "||**||**|*" ，查询 [3, 8][3,8] ，表示的是子字符串 "*||**|" 。子字符串中在两支蜡烛之间的盘子数目为 22 ，子字符串中右边两个盘子在它们左边和右边 都 至少有一支蜡烛。 请你返回一个整数数组 answeranswer ，其中 answer[i]answer[i] 是第 ii 个查询的答案。
示例 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^53<=s.length<=105
s只包含字符'*'和'|'。- 1 <= queries.length <= 10^51<=queries.length<=105
- queries[i].length == 2queries[i].length==2
- 0 <= lefti <= righti < s.length0<=lefti<=righti<s.length
二分 + 前缀和
对于任意一个查询 [a, b][a,b] 而言，我们需要统计所有左边和右边能够找到蜡烛的盘子数量。
一个自然的想法是：找到区间 [a, b][a,b] 两边缘的蜡烛，分别记为 cc 和 dd，显然区间 [c, d][c,d] 内的盘子都是需要被统计的。
因此，我们可以对字符串 s 进行从前往后的扫描，将所有的蜡烛下标添加到数组（数组严格递增），并预处理出盘子的「前缀和」数组。
然后处理询问时的「找区间 [a, b][a,b] 边缘蜡烛」操作可通过对数组「二分」来做，而「查询区间 [c, d][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的长度为 nn，qs长度为 mm。统计所有的蜡烛并存入list的复杂度为 O(n)O(n)；预处理前缀和数组复杂度为 O(n)O(n)；处理单个询问需要进行两次二分（蜡烛数量最多为 nn），复杂度为 O(\log{n})O(logn)，共有 mm 个询问需要处理，复杂度为 O(m * \log{n})O(m∗logn)。整体复杂度为 O(n + m\log{n})O(n+mlogn) - 空间复杂度：O(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; } } 复制代码
- 时间复杂度：O(n + m)O(n+m)
- 空间复杂度：O(n)O(n)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.2055 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
