如果您已经有思路了，或者是N刷了，可以先自己写一遍。

题目分析

“接雨水”（Trapping Rain Water）问题是一个经典的计算机科学问题，在算法设计中常用作演示如何利用数据结构解决实际问题。在这个问题中，你需要计算在非均匀高度的柱子之间能够积累多少雨水。

解题思路

使用单调栈是解决接雨水问题的另一种有效方法。单调栈可以帮助我们跟踪可能存储雨水的凹槽。

具体地说，我们将使用一个单调递减栈来存储那些可能形成边界的柱子的索引，从而帮助我们计算能够接住的雨水量。

Java解法

下面是使用Java语言的解法：

class Solution {
    public int trap(int[] height) {
        // 创建一个栈来存储索引
        Stack<Integer> stack = new Stack<>();
        int water = 0, i = 0;  // water 用于累计积水量，i 用于遍历数组
        
        // 遍历数组中的每一个元素
        while (i < height.length) {
            // 当栈不为空，且当前柱子的高度大于栈顶柱子的高度时
            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                // 弹出栈顶元素
                int top = stack.pop();

                // 如果栈为空，退出循环
                if (stack.isEmpty()) {
                    break;
                }

                // 计算当前位置与栈顶位置之间的距离
                int distance = i - stack.peek() - 1;
                // 计算当前位置和新的栈顶位置的柱子高度的最小值与弹出柱子的高度之差，即界限高度
                int boundedHeight = Math.min(height[i], height[stack.peek()]) - height[top];
                // 根据界限高度和距离计算水量，并累加到总水量中
                water += distance * boundedHeight;
            }
            // 将当前索引压入栈中
            stack.push(i++);
        }
        
        // 返回计算得到的总水量
        return water;
    }
}

在这个代码中：
- 我们首先创建一个栈来保存那些可能会形成凹槽的柱子的索引。
- 随着数组的遍历，我们比较当前柱子的高度与栈顶柱子的高度。如果当前柱子的高度大于栈顶柱子的高度，这表示我们可能找到了一个右边界。
- 栈顶元素弹出后，我们计算这个槽可以存储的水量。计算水量需要根据栈中新的栈顶元素和当前元素的距离，以及两者的高度差。
- 最后，每个处理的柱子的索引被压入栈中，等待后续可能的处理。
- 遍历完所有柱子后，返回累计的水量。

时间复杂度

时间复杂度为 O(n)，其中 n 是数组 height 的长度。每个元素最多被压入栈一次，并且也被从栈中弹出一次。虽然看起来有两层循环（外层循环遍历数组，内层循环处理栈中元素），但内层循环中的元素弹出操作总共不会超过 n 次（即数组长度），因为每个元素只会被压入和弹出一次。因此，总体操作数是线性的。

空间复杂度

空间复杂度为 O(n)。这是因为在最坏的情况下，如果输入数组是单调递减的，那么所有的元素都会被压入栈中并一直保留到最后，因此栈的大小可能会增长到与输入数组的长度一致。

综上所述，使用单调栈的方法在处理此类问题时既高效又直观，虽然在空间上需要一定的额外开销，但在时间上保证了效率。

References

42. 接雨水 ↩︎

趣味算法题

单调栈：接雨水