42-接雨水

LeetCode 42. Trapping Rain Water

LeetCode-42

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Example 1:

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

method: 单调栈

维护一个从栈底到栈顶递减的栈，如果下一个值不满足递减，就要出栈计算雨水值
注意这里出栈要用while，相同的元素要全部出栈再计算

雨水高度计算：不满足递减的height[i]，与左边维持可积水的height[st.top()]中的较小值，减去出栈的height[topIdx]
雨水宽度计算：左开右开区间(st.top,i)的宽度，即i-st.top()-1

一个雨水计算完后相当于把这个坑填上

int trap(vector<int>& height) {
    stack<int> st;
    int ret = 0;
    for (int i = 0; i < height.size(); ++i) {
        while (!st.empty() && height[i] > height[st.top()]) {
            int topVal = height[st.top()];
            while (!st.empty() && height[st.top()] == topVal) st.pop();
            // 相同的高度要全部出栈
            // 判断左边有没有值，也就是栈要非空才能接水
            if (!st.empty()) {
                int h = min(height[i], height[st.top()]) - topVal;
                int w = i - st.top() - 1;
                ret += h * w;
            }
        }
        st.push(i);     // 记得push
    }
    return ret;
}

两个容易错的：

1. 要记得push(i)
2. 计算高度的时候要减去topVal