leetcode Trapping Rain Water

leetcode 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.

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!

题目地址:leetcode Trapping Rain Water

题意:给定数组A,A[i]表示第i个位置的高度,求可以盛放雨水的容量。(参考图)

思路:

对于A[i],如果A[i]这个位置可以装水,那么左右两边必定各有一个数大于A[i], (设为left[i]和right[i])且这个位置能放的量最多为min(left[i],right[i]) – A[i]

因此一个直接的想法就是维护两个数组,分别为左右两边的最大值:

C++

另一种写法:

上面的写法left[i]是不包括当前i这个元素的,如果要包括,则可以写成下面这样:

但是最后的更新要改成min(left[i – 1],right[i + 1]) – A[i]

Java

 

但能用双指针做得更好:

两个指针L=0 和 R =n-1, 维护左边最大max_left和右边最大值max_right,如果 A[L] < A[R] 那么,那么若max_left > A[L],那么A[L]这个位置可以装水,因为右边A[R]>A[L],并且左边有元素也比较大,所以能装的水为max_left – A[L],然后L++

A[L]  > A[R]同理,是和A[R]进行比较 ,更新ans, 然后R–

那么A[L] = A[R]的情况呢?任意的归为上面两种情况均可。这里假设归为第一种情况。那么max_left>A[L],但是右边的A[L] = A[R]一定能装水么?答案是肯定的。假如不能装水,说明大于L的范围中,均有A[i] <= A[L](i = L+1…n),但是max_left > A[L], 就是说不可能进入这个分支中。而如果进入了这个分支,那么说明此时R右边必然有比当时max_left来得大的元素。

C++

python

 

另一种写法:

left和right为当前的元素位置,维护left_max和right_max分别代表left左边最大值和right右边的最大值。

若left_max < right_max,则说明left只能装left_max – height[left]了(当然需要left_max > height[left]),并让left +=1

否则,说明right只能装right_max – height[right]了(也需要right_max > height[right]),然后right-=1

更多题解可以查看: https://www.hrwhisper.me/leetcode-algorithm-solution/

本博客若无特殊说明则由 hrwhisper 原创发布
转载请点名出处:细语呢喃 > leetcode Trapping Rain Water
本文地址:https://www.hrwhisper.me/leetcode-trapping-rain-water/

听说长得好看的已经打赏了

Leetcode , . permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *