• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

【leetcode42】接雨水

开发技术 开发技术 4小时前 1次浏览

https://leetcode-cn.com/problems/trapping-rain-water/submissions/

分析

可以看出,接雨水最后形成的图形必然是塔状图形,两侧呈阶梯状,每个“台阶”都是height序列从两端开始在这个高度的第一列,因此可以先算出最终的塔状图形面积,再减去所有的非雨水面积即可。

class Solution {
public:
    int trap(vector<int>& height) {
        int lh=height.size(),l=0,r=lh-1,pre_height=0;
        long long ans=0;
        while(l<=r)
        {
            if(height[l]<=height[r])
            {
                int now_height=height[l]-pre_height;
                pre_height=height[l];
                ans+=now_height*(r-l+1);
                while(height[l]<=pre_height)
                {
                   l++;
                   if(l>r)break;
                }
            }
            else
            {
                int now_height=height[r]-pre_height;
                pre_height=height[r];
                ans+=now_height*(r-l+1);
                while(height[r]<=pre_height)
                {
                   r--;
                   if(l>r)break;
                }
            }
        }
        for(int i=0;i<lh;i++)
        {
            ans-=height[i];
        }
        return ans;
    }
};

程序员灯塔
转载请注明原文链接:【leetcode42】接雨水
喜欢 (0)