42. 接雨水

Problem: 42. 接雨水

思路

经典的单调栈，但是要找到栈顶元素左右第一个大于他的元素，因为我们使用单调栈，可以知道在单调栈中栈顶元素的前一个元素，就是左边第一个大于他的元素。

另外，if(height[i] == height[st.top()])的情况可以先弹出，再加入。

我们计算面积是计算一个宽度，并不是高度，就像下面的箭头一样。

还有要注意的地方就是，在计算宽度的时候要弹出元素，不要忘记判空。

Code

[]

class Solution {
public:
    int trap(vector<int>& height) {
        stack<int> st;
        int res = 0;
        st.push(0);
        for(int i = 1; i < height.size(); i++) {
            if(height[i] < height[st.top()]) st.push(i);
            else {
                while(!st.empty() && height[i] > height[st.top()]) {
                    int mid = st.top();
                    st.pop();
                    if(!st.empty()) {
                        int left = st.top();
                        int right = i;
                        int min = std::min(height[left],height[right]);
                        res += (min - height[mid]) * (right - left - 1);
                    }
                }
                st.push(i);
            }
        }
        return res;
    }
};