leetcode 42. 接雨水

淡淡的烟草味﹌ 2023-07-05 14:53 7阅读 0赞

### 解题思路 ###

思路其实很清楚。计算加上水以后的面积，然后减去原始的面积（即高度之和）。剩下的就是能接的雨水。  
问题是如何计算加上水以后的面积？  
有一个单调栈的思路。从左开始遍历(设top=l)，直到遇到比height\[top\]大的height\[i\].意味着，从top到i之间可以构成以height\[top\]为高，底为i-top 的长方形。此时可以计算面积。  
如果最高的在中间怎么办？其实很简单，再重最右边扫描一遍到top即可。  
复杂度，最坏情况下,o(1.5n) 常数还是比较小的。  
不过写起来比较麻烦。不建议使用该种方法。

### 代码 ###

class Solution { 
    public:
        int trap(vector<int>& height) { 
            int black=0;
            int n=height.size();
            if(n==0||n==1) return 0;
            for(int i=0;i<n;i++)
            { 
                black+=height[i];
            }
            int l=0,r=n-1;
            while((l+1)<n&&height[l]<=height[l+1]) l++;
            while((r-1)>=0&&height[r]<=height[r-1]) r--;
            if(l>=r) return 0;
            int top=l;
            int ans=0;
            bool f=0;
            for(int i=l;i<=r;i++)
            { 
                while(i<=r&&height[i]<=height[top]) i++;
                if(i<=r)
                { 
                    ans+=(i-top)*height[top];
                    top=i;
                }
                else
                { 
                    if(height[i-1]==height[top])
                    { 
                        ans+=(i-top)*height[top];
                        f=1;
                    }
                }
            }
            //cout<<ans<<endl;
            if(top<r&&f==0)
            { 
                int k=r;
                for(int j=r;j>=top;j--)
                { 
                    while(j>=top&&height[j]<=height[k]) j--;
                    if(j>=top)
                    { 
                        ans+=(k-j)*height[k];
                        k=j;
                    }
                    else
                    { 
                        if(height[j+1]==height[k])
                        { 
                            ans+=(k-j)*height[k];
                            k=j+1;
                            f=1;
                        }
                    }
                }
            }
            if(f==0)  ans+=height[top];
            for(int i=0;i<l;i++) ans+=height[i];
            for(int j=r+1;j<n;j++) ans+=height[j];
            return ans-black;
        }
    };