题目描述

在刷leetcode暑期打卡，遇到这道题看了好几遍录像终于搞懂了，记录一下

样例

首先创建一个 递减 的单调栈，当有大于栈顶元素加入的时候，取出栈顶元素并弹出。此时这一层的长度是i - t - 1,因为两边都不算所以要-1； 乘以高度差之后加到res中，用被弹出的栈顶元素更新last。循环至所有栈内比新加入高度低的块所围成的面积都被加入。

之后，如果栈内不空，说明栈内有比新加入块更高的块，那么需要加上一段新加入块高度 减 last的一段面积。

为什么每重循环last都要重新赋为0呢？ 因为每次新一轮循环的时候，第一个不单调递减的块与上一个位置的距离总是0，last会自动更新成栈内低点。

class Solution {
public:
    int trap(vector<int>& height) {
        int res = 0;
        stack<int> stk;

        for (int i = 0; i < height.size(); i ++)
        {
            int last = 0;
            while (stk.size() && height[stk.top()] <= height[i]) 
            {
                int t = stk.top();
                stk.pop();
                res += (i - t - 1) * (height[t] - last);
                last = height[t];   // 枚举新加入的比栈顶高的几层
            }
            if (stk.size()) res +=  (i - stk.top() - 1) * (height[i] - last); 
            // 加上左边比新加入高的一层，但还是右边减去last。。 
            stk.push(i);
        }

        return res;


    }
};