[LeetCode Hot 100] LeetCode42. 接雨水

题目描述

思路一：单调栈

柱子的高度递减的时候是装不了水的，当碰到第一个比之前高的柱子才可以装水。
此时计算栈顶索引能装的水：

• 宽：i - left - 1(这个left为栈顶元素pop之后的peek值)
• 高：min(height[left], height[i]) - height[top]
• 该题维护的是一个单调递减栈

方法一：对应思路一

class Solution {
    public int trap(int[] height) {
        if (height == null || height.length <= 2) return 0;

        // 这里维护的是一个单调递减栈
        Deque<Integer> stack = new ArrayDeque<>();
        int res = 0;

        for (int i = 0; i < height.length; i ++) {
            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                int top = stack.pop();
                // 这行代码正好能解决示例1中索引0为0的情况
                if (stack.isEmpty()) break;
                int h = Math.min(height[i], height[stack.peek()]) - height[top];
                int w = i - stack.peek() - 1;
                res += h * w;   
            }
            stack.push(i);
        }
        return res;
    }
}