【LeetCode每日一题】面试题 17.21. 直方图的水量

class Solution {
public:
    int trap(vector<int>& height) {
        stack<int> st;
        int n = height.size();
        int ans = 0;
        for (int i=0;i<n;i++) {
            while (!st.empty() && height[st.top()]<=height[i]) {
                int prev_height = st.top();
                st.pop();
                if (st.empty()) break;
                int w = i - st.top() - 1;
                int left_height = height[st.top()];
                int h = min(left_height,height[i]) - height[prev_height];
                ans += w*h;
            }
            st.push(i);
        }
        return ans;
    }
};