本页目录

LeetCode 42.接雨水

0 views · 2024-07-02

原题链接：接雨水

维护一个单调递减栈（存放下标），考虑入栈元素对应的高度，大于等于栈顶元素对应的高度的情况，此时需要出栈：
如果栈中仅剩一个元素，那么无法形成凹槽，直接出栈，入栈；
如果栈中有多个元素，记左侧的元素为，则弹出时要累计和之间的额外矩形“存水量”，这个矩形的高度为，宽度为。

C++
#define N 20005
class Solution {
public:
    int trap(vector<int>& height) {
        int ans=0,n=height.size();
        int st[N],top=-1;
        for(int i=0;i<n;i++)
        {
            while(top>=0&&height[st[top]]<=height[i])
            {
                top--;
                if(top>=0)
                {
                    int h=min(height[st[top]],height[i])-height[st[top+1]];
                    int w=i-st[top]-1;
                    ans+=w*h;
                }
            }
            top++,st[top]=i;
        }
        return ans;
    }
};