← 返回编程题库
coding-trapping-volume-between-quotes中等免费版2000ms未尝试

局部高点报价之间的最大囤积体积

Trapping Volume Between Local-Max Quotes

开始编码

微结构组对一档标的每个 tick 记录整数中间价,把一整天的报价存进列表 quotes。他们想要一个盘前的快速上限指标:如果价格在每段局部高点之间都完美地走出回撤形态,理论上能在这些局部高点之间囤住多少体积? 把每个 tick 想象成一根高度为 quotes[i] 的直立长条,肩并肩排好;从上面往下倒水,问问凹陷处会接住多少水。这个一次性、日频的统计量被组里用来比较不同标的的「盆地化程度」——囤积体积越大的,说明它的中间价相对周边的局部高点偏离得越远。

请实现 solution(quotes: list[int]) -> int,返回总囤积体积。位置 i 上方的水量等于 min(left_max, right_max) - quotes[i](只在结果为正时累加),其中 left_max 是下标 0..i 中的最大报价,right_max 是下标 i..n-1 中的最大报价。把所有位置加总即可。边界:len(quotes) < 3 时无法形成盆地(返回零);全等报价、严格单调递增、严格单调递减序列都囤不到水(返回零)。

示例solution([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]) 返回 6。把每个位置的 min(left_max, right_max) - quotes[i] 写出来是 0, 0, 1, 0, 1, 2, 1, 0, 0, 1, 0, 0,加起来正好是 6——这就是 LeetCode 42 那道祖传题的答案。再看 solution([3, 0, 3]):中间一个深谷,两侧墙都是 3,中间格囤水 min(3,3) - 0 = 3 个单位。第三个例子 solution([1, 2, 3, 4, 5]) 返回 0:严格递增意味着任何位置右边都没有更高的挡墙,水都从右边漏走了。

朴素做法「对每个位置往左、往右各扫一遍找最大值」是 O(n²),在 n = 10⁵ 时会超时。正确思路要么用单调栈——每来一个更高的右墙就把栈中较矮的盆底逐个弹出结算(每个下标入栈出栈各一次 → O(n)),要么用双指针扫——总是推进运行最大值较小的那一侧(较矮的一侧就是瓶颈,水位已经被它锁死 → 同样 O(n))。两种方法都是 O(n) 时间、O(1) 额外空间(单调栈版本在极端递增前缀下辅助空间是 O(n))。

约束条件

  • 0 ≤ len(quotes) ≤ 100000
  • 0 ≤ quotes[i] ≤ 10⁹(每个 tick 上的非负整数中间价)
  • 长度为 0、1、2 时无法形成盆地——返回 0
  • 全等报价、严格单调递增、严格单调递减都囤不到水——返回 0
  • 返回值为 int,要求严格相等比较

样例

Case 1 · classic LeetCode 42 silhouette

输入: [[0,1,0,2,1,0,1,3,2,1,2,1]]

期望: 6

经典 [0,1,0,2,1,0,1,3,2,1,2,1] 形状:每个位置能囤积的水量等于 min(左侧最高, 右侧最高) - 当前高度。把每个位置的水量加起来正好是 6。

Case 2 · single deep valley between two equal peaks

输入: [[3,0,3]]

期望: 3

中间一个深谷,两侧高度都是 3。中间那一格能囤 min(3,3)-0=3 个单位的水。

Case 3 · asymmetric trap with multiple low ticks

输入: [[4,2,0,3,2,5]]

期望: 9

下标 1..4 的高度分别为 2,0,3,2,对应能囤水量 min(4,5)-2=2、min(4,5)-0=4、min(4,5)-3=1、min(4,5)-2=2,合计 9。注意右侧最高 5 大于左侧最高 4,所以瓶颈是 4。

最近提交

还没有提交记录。

编码区

实现 solution(...)。本地运行当前支持 Python 可见样例;服务端提交会运行可见样例和隐藏测试。

加载编辑器...
计时0:00

默认展示公开样例。点击「运行样例」后会在这里显示实际输出;点击「提交评测」会进入隐藏测试。

Case 1 · classic LeetCode 42 silhouette

输入: [[0,1,0,2,1,0,1,3,2,1,2,1]]

期望: 6

经典 [0,1,0,2,1,0,1,3,2,1,2,1] 形状:每个位置能囤积的水量等于 min(左侧最高, 右侧最高) - 当前高度。把每个位置的水量加起来正好是 6。

Case 2 · single deep valley between two equal peaks

输入: [[3,0,3]]

期望: 3

中间一个深谷,两侧高度都是 3。中间那一格能囤 min(3,3)-0=3 个单位的水。

Case 3 · asymmetric trap with multiple low ticks

输入: [[4,2,0,3,2,5]]

期望: 9

下标 1..4 的高度分别为 2,0,3,2,对应能囤水量 min(4,5)-2=2、min(4,5)-0=4、min(4,5)-3=1、min(4,5)-2=2,合计 9。注意右侧最高 5 大于左侧最高 4,所以瓶颈是 4。