首页 > itarticle > 【leetcode】 trapping rain water

【leetcode】 trapping rain water

admin 11月 13, 2020 0

地址

https://leetcode.com/problems/trapping-rain-water/description/

题目

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

思路

假如从i开始，找到后面第一个大于等于h[i]的数，然后计算答案。如何后面没有大于等于h[i]的数，那么就找到i后面最大的一个数，计算答案。

代码

class  {
public:
    int trap(vector<int>& h) {
        if(h.size()==0)
            return 0;
        int n=h.size(),ans=0,pre[100000];
        pre[0]=h[0];
        for(int i=1;i<n;i++) pre[i]=pre[i-1]+h[i];
        for(int i=0;i<n-1;i++)
        if(h[i])
        {
            int d=-1,dh,ff=0;
            for(int j=i+1;j<n;j++)
            if(h[j]>=h[i])
            {
                ans+=min(h[i],h[j])*(j-i-1)-(pre[j-1]-pre[i]);
                i=j-1,ff=1;
                break;
            }
            else if(d<0||h[j]>dh)
                d=j,dh=h[j];
            if(d>0&&!ff)
                ans+=dh*(d-i-1)-(pre[d-1]-pre[i]),i=d-1;
        }
        return ans;
    }
};