接雨水1

题目描述

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。

示例:

输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

方法一

class Solution {
public:
    int trap(vector<int>& height) {
       int res = 0,mx=0,n = height.size();
        vector<int> dp(n,0);
        for(int i=0;i<n;++i)
        {
            dp[i] = mx;
            mx=max(mx,height[i]);
        }
        mx = 0;
        for(int i=n-1;i>=0;--i)
        {
            dp[i] = min(dp[i],mx);
            mx = max(mx,height[i]);
            if(dp[i]>height[i])
                res += dp[i]-height[i];
        }
        return res;
    }
};

方法二

class Solution{
  public:
    int trap(vector<int>& height){
        int res = 0,l=0,r =height.size()-1;
        while(l<r)
        {
            int mn = min(height[l],height[r]);
            if(mn == height[l])
            {
                ++l;
                while(l<r&& height[l]<mn)
                {
                    res += mn-height[l++];
                }
            }else{
                --r;
                while(l<r&&height[r]<mn)
                {
                    res += mn-height[r--];
                }
            }
        }
        return res;
    }
};

方法三

class Solution{
  public:
    int trap(vector<int>& height){
        int l=0,r=height.size()-1,level=0,res=0;
        while(l<r)
        {
            int lower=height[(height[l]<height[r])? l++:r--];
            level = max(level,lower);
            res+= level-lower;
        }
        return res;
    }
};

方法四

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