【LeetCode 热题 100】42. 接雨水——（解法三）单调栈

Problem: 42. 接雨水

整体思路

采用 单调栈 的方法来解决经典的 “接雨水” 问题。其核心目标是计算一个由非负整数代表的高程图（height数组）能够 trapping（接住）多少单位的雨水。

算法的整体思路可以分解为以下几个步骤：

1. 核心数据结构：

   • 算法使用一个 栈（Deque 实现）来存储柱子的 索引。
   • 这个栈有一个关键特性：它始终保持 单调递减。也就是说，从栈底到栈顶，其索引对应的柱子高度是严格递减的（或非严格，取决于具体实现，本代码中是 h[s[top]] > h[s[top-1]] 的趋势，但在遇到相等高度时，会先处理，所以可以理解为单调递减栈）。

2. 遍历与处理：

   • 代码从左到右遍历 height 数组中的每一个柱子（currentIndex）。
   • 对于每个当前柱子 currentHeight，它会与栈顶的柱子高度进行比较。

3. 凹槽识别与计算：

   • 触发条件：当 currentHeight 大于 栈顶索引对应的柱子高度时，一个潜在的“凹槽”或“水坑”的右边界就被找到了。
   • 计算逻辑：
     1. 此时，栈顶元素 decreasingHeightStack.peek() 对应的柱子高度是凹槽的底部。我们将其弹出（bottomIndex）。
     2. 弹出后，如果栈非空，那么新的栈顶元素 decreasingHeightStack.peek() 就是凹槽的 左边界（leftBoundaryIndex）。
     3. 当前的柱子 currentIndex 则是凹槽的 右边界。
     4. 有了左边界、右边界和底部，就可以计算这个特定凹槽能接的雨水：
        • 宽度 (distance)：rightBoundaryIndex - leftBoundaryIndex - 1。
        • 高度 (boundedHeight)：由左右边界中较矮的那个决定，即 min(左边界高度, 右边界高度) - 底部高度。
        • 水量：宽度 * 高度。
     5. 将计算出的水量累加到 totalWater 中。
   • 这个 while 循环会持续进行，直到栈为空或者栈顶柱子不再低于当前柱子。这可以处理类似 [2, 1, 0, 3] 这样，一个右边界（3）可以和多个底部（0, 1）形成多个层次的凹槽。

4. 栈状态维护：

   • 在 while 循环结束后（即所有能与当前柱子形成凹槽的更矮的柱子都已被处理完毕），将当前柱子的索引 currentIndex 压入栈中。这维持了栈的单调递减特性，为后续的计算做准备。

5. 结果返回：

   • 遍历完所有柱子后，totalWater 中就包含了所有凹槽累加的雨水总量，将其返回。

该算法通过维护一个单调递减的索引栈，巧妙地在找到一个“右边界”时，回溯并计算所有以它为右边界的、能够形成的凹槽的雨水量。

完整代码

class Solution {public int trap(int[] height) {// 进行边界检查，如果数组为空或长度为0，则无法接水，直接返回0。if (height == null || height.length == 0) {return 0;}// 用于累计总的雨水容量，初始化为0。int totalWater = 0; // 使用一个双端队列 Deque 作为栈，存储柱子的索引。// 这个栈的核心特性是，从栈底到栈顶，其索引对应的柱子高度是单调递减的。// 存储索引而不是高度，是为了方便计算凹槽的宽度。Deque<Integer> decreasingHeightStack = new ArrayDeque<>(); // 遍历整个高度数组，currentIndex 是当前柱子的索引。for (int currentIndex = 0; currentIndex < height.length; currentIndex++) { // 获取当前索引对应的柱子高度。int currentHeight = height[currentIndex]; // 当栈不为空，且当前柱子的高度(currentHeight)大于栈顶索引对应的柱子高度时，// 表明找到了一个凹槽的右边界，可以计算接水量。while (!decreasingHeightStack.isEmpty() && height[decreasingHeightStack.peek()] < currentHeight) {// 弹出栈顶索引，这个索引对应的柱子是凹槽的底部。int bottomIndex = decreasingHeightStack.pop(); int bottomHeight = height[bottomIndex]; // 凹槽底部的高度。// 如果弹出底部后栈变为空，说明底部左侧没有更高的柱子形成左边界，// 无法构成一个完整的凹槽来接水，因此跳出当前while循环。if (decreasingHeightStack.isEmpty()) {break;}// 此时，新的栈顶索引就是凹槽的左边界。int leftBoundaryIndex = decreasingHeightStack.peek(); int leftBoundaryHeight = height[leftBoundaryIndex]; // 左边界的高度。// 计算凹槽的宽度，即右边界索引减去左边界索引，再减1（因为边界本身不计入宽度）。int distance = currentIndex - leftBoundaryIndex - 1;// 计算能够接水的高度。水的高度由左右两个边界中较矮的那个决定，// 并且需要减去底部的高度。int boundedHeight = Math.min(leftBoundaryHeight, currentHeight) - bottomHeight;// 计算这个凹槽能接的雨水量（面积 = 宽度 * 高度），并累加到总水量中。totalWater += distance * boundedHeight;}// 将当前柱子的索引压入栈中。// 经过上面的while循环，所有比当前柱子矮的栈内柱子都已被处理，// 因此压入后仍然能维持栈的单调递减特性。decreasingHeightStack.push(currentIndex);}// 遍历结束后，返回累计的总雨水量。return totalWater;}
}

时空复杂度

时间复杂度：O(N)

1. 外层循环：for 循环从 0 遍历到 height.length - 1，它会执行 N 次，其中 N 是数组 height 的长度。这是 O(N) 的。
2. 内层循环：while 循环虽然嵌套在 for 循环内部，但它的总执行次数是有限的。每个柱子的索引最多被 压入（push）栈一次 和 弹出（pop）栈一次。
3. 摊还分析：对于 for 循环的每次迭代，while 循环可能会执行多次 pop 操作。但是，从整个算法的生命周期来看，push 和 pop 的总操作次数都不能超过 N 次。由于 while 循环中的操作（pop, peek, 数学计算）都是 O(1) 的，所以所有 while 循环的总工作量加起来是 O(N) 的。

综合分析：整个算法的时间复杂度由 for 循环（O(N)）和所有 while 循环的总工作量（O(N)）构成。因此，总的时间复杂度是 O(N) + O(N) = O(N)。

空间复杂度：O(N)

1. 主要存储开销：算法使用了额外的空间，即 decreasingHeightStack 这个栈。
2. 最坏情况：在最坏的情况下，栈需要存储所有柱子的索引。这种情况发生在输入数组 height 是一个严格递减序列时（例如 [10, 9, 8, 7, 6]）。在这种场景下，每个柱子的索引都会被压入栈，并且在遍历结束前都不会被弹出。
3. 结论：因此，栈的大小可以达到 N。其他变量（如 totalWater, currentIndex 等）只占用 O(1) 的空间。

综合分析：算法所需的额外空间主要由栈决定，其最大深度可以为 N。因此，空间复杂度为 O(N)。

参考灵神