【LeetCode】42. Trapping Rain Water

时间:2023-03-08 15:53:12
【LeetCode】42. Trapping Rain Water

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.

【LeetCode】42. Trapping Rain Water

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!

双指针left,right分别从首尾开始扫,记当前left指针遇到的最大值为leftWall,right指针遇到的最大值为rightWall

(1)leftWall <= rightWall

left前进一个位置。

对于left指针指向的位置,若存在被trap,则被trap的值为(leftWall-A[left])。

解释如下:

a.如果left与right之间不存在比leftWall大的值,那么i位置trap的值就取决与leftWall与rightWall的较小值,也就是leftWall

b.如果left与right之间存在比leftWall大的值,其中离leftWall最近的记为newLeftWall,那么i位置trap的值就取决与leftWall与newLeftWall的较小值,也就是leftWall

(2)leftWall > rightWall

right后退一个位置。

对于right指针指向的位置,被trap的值为(rightWall-A[right])。

解释同上。

class Solution {
public:
int trap(int A[], int n) {
int ret = ;
int left = ;
int right = n-;
int leftWall = A[left];
int rightWall = A[right];
while(left < right)
{
if(leftWall <= rightWall)
{
left ++;
if(A[left] <= leftWall)
ret += (leftWall - A[left]);
else
leftWall = A[left];
}
else
{
right --;
if(A[right] <= rightWall)
ret += (rightWall - A[right]);
else
rightWall = A[right];
}
}
return ret;
}
};

【LeetCode】42. Trapping Rain Water