type
status
date
slug
summary
tags
category
icon
password
创建时间
May 3, 2025 02:15 AM
给你一个长桌子，桌子上盘子和蜡烛排成一列。给你一个下标从 0 开始的字符串
s ，它只包含字符 '*' 和 '|' ，其中 '*' 表示一个 盘子 ，'|' 表示一支 蜡烛 。同时给你一个下标从 0 开始的二维整数数组
queries ，其中 queries[i] = [lefti, righti] 表示 子字符串 s[lefti...righti] （包含左右端点的字符）。对于每个查询，你需要找到 子字符串中 在 两支蜡烛之间 的盘子的 数目 。如果一个盘子在 子字符串中 左边和右边 都 至少有一支蜡烛，那么这个盘子满足在 两支蜡烛之间 。- 比方说，
s = "||**||**|*"，查询[3, 8]，表示的是子字符串"*||*|"。子字符串中在两支蜡烛之间的盘子数目为2，子字符串中右边两个盘子在它们左边和右边 都 至少有一支蜡烛。
请你返回一个整数数组
answer ，其中 answer[i] 是第 i 个查询的答案。一、前缀和——1.1 前缀和基础
二分查找和前缀和
想了半天，没有什么头绪。知道用前缀和找盘子数量，但是题目要求盘子两边都至少需要一根蜡烛。这让我没有头绪，不知道怎么做。看了题解，才发现使用一个数组存储每个蜡烛的位置，然后再询问时，使用二分查找得到区间内，被左右蜡烛位置。
参考 宫水三叶
使用库函数的二分查找函数的技巧！！！
如果本题使用二分查找，也可以不使用前缀和来做。例如，下面这幅图。我们存储每个蜡烛的位置后，可以得到区间的大小和区间中的蜡烛多少。
区间的大小：
list[r] - list[l] + 1蜡烛的多少就是
list 中的长度：r - l + 1
完全前缀和
为什么左边界从右侧选，右边界从左侧选？
因为，左边界从右侧选，才能保证选择的值是在整个大区间之中的！！！
