Leetcode 42 Trapping Rain Water

triplebee

发布于 2018-01-12 15:06:19

4440

发布于 2018-01-12 15:06:19

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!

左右两点，小的向中间缩，同时小的一侧与那一侧最大值的高度差，得出的为这个点的水深。

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

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2016-09-07 ，如有侵权请联系 cloudcommunity@tencent.com 删除

case