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