Leetcode 42 Trapping Rain Water

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.

image.png

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!

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

代码语言：javascript复制

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;
    }
};

case image map return

0 人点赞