LeetCode 42. Trapping Rain Water

Problem

LeetCode 42. Trapping Rain Water

1. 题目简述

给出一组非负整数表示地形，每一个竖条的宽度为1，计算下雨后，地形中能储存多少水。例如：

Example:

Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

2. 算法思路

相关问题：

1. LeetCode 503. Next Greater Element II
2. LeetCode 556. Next Greater Element III
3. LeetCode 739. Daily Temperatures(无解析)

monotonous stack（单调栈）

自己复习的时候直接看yxc的题解21分40秒，有图才能更清晰。这里不做过多的解释了，很难讲。

其实这道题是属于单调栈的一种不常见的case，也是属于单调栈的一种，我们每次遇到一个“洼地”的时候其实需要计算一下可以存多少雨水。

class Solution {
    public int trap(int[] height) {
        Stack<Integer> stack = new Stack();
        int n = height.length, res = 0;

        for (int i = 0; i < n; i++) {
            // last用来记录上一次的高度，这里初始化为0是为了防止边界情况，首次pop的时候不计算面积。
            int last = 0;
            while (!stack.isEmpty() && height[i] >= height[stack.peek()]) {
                // 这里首次计算的时候，i - stack.peek() - 1一定为0，这里是做了一个mapping。
                res += (height[stack.peek()] - last) * (i - stack.peek() - 1);
                last = height[stack.pop()];
            }

            // 如果pop完以后发现左侧还有一个更高的，把小尾巴计算上（以【4，2，3】为例）
            if (!stack.isEmpty()) {
                res += (i - stack.peek() - 1) * (height[i] - last);
            }

            stack.push(i);
        }

        return res;
    }
}