[!info] related notes 算法面试题型 MOC 栈 单调栈

接雨水

题目链接：https://leetcode.cn/problems/trapping-rain-water/

题型判断

这题有两种主流做法：

• 双指针
• 单调栈

如果从栈角度理解，它属于“单调栈 + 凹槽结算”题。

单调栈思路

维护一个按高度非递增的栈，栈里放下标。柱高按题意非负，每根柱宽为 1；相等高度可以保留。

当当前柱子 height[i] 比栈顶更高时，说明出现了右边界，可以尝试结算一段雨水。

弹出中间低柱 mid 后：

• 新栈顶 left 是左边界
• 当前 i 是右边界
• mid 是凹槽底部

可接水高度：

min(height[left], height[i]) - height[mid]

宽度：

i - left - 1

双指针思路

双指针做法的核心是：

• 哪一侧更低，就移动哪一侧
• 移动时用该侧历史最高值结算当前位置能接的水

这是这题最常用的面试写法。

分析

下面先比较当前左右柱高，再移动较低一侧并更新该侧最高值。水量按列累计，和栈法分层累计是不同的计算视角，不应混用两者的宽度公式。

function trap(height: number[]): number {
    const n = height.length;
    if (n < 3) return 0;
    let left = 0, right = n - 1;
    let leftMax = height[left], rightMax = height[right];
    let ans = 0;
    while (left < right) {
        if (height[left] <= height[right]) {
            left++;
            leftMax = Math.max(leftMax, height[left]);
            const count = leftMax - height[left];
            if (count > 0) ans += count;
        } else {
            right--;
            rightMax = Math.max(rightMax, height[right]);
            const count = rightMax - height[right];
            if (count > 0) ans += count;
        }
    }
    return ans;
}

单调栈 JavaScript

var trap = function(height) {
    const stack = [];
    let ans = 0;

    for (let i = 0; i < height.length; i++) {
        while (stack.length && height[i] > height[stack[stack.length - 1]]) {
            const mid = stack.pop();

            if (!stack.length) break;

            const left = stack[stack.length - 1];
            const h = Math.min(height[left], height[i]) - height[mid];
            const w = i - left - 1;
            ans += h * w;
        }

        stack.push(i);
    }

    return ans;
};

双指针时间 O(n)、额外空间 O(1)；单调栈时间 O(n)、额外空间 O(n)。栈法弹出底部后若没有左边界，就不能结算水量；等高层可能贡献 0。

一句话总结

单调栈做法里，被弹出的柱子不是边界，而是凹槽底部；左右边界由弹栈后的栈顶和当前柱子共同决定。