0%

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++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
int trap(vector<int>& height) {
int n = height.size();
vector<int> left(n, 0), right(n, 0);
for(int i = 1; i < n; ++i)
left[i] = max(left[i - 1], height[i - 1]);
for(int i = n - 2; i >= 0; --i)
right[i] = max(right[i + 1], height[i + 1]);

int ans = 0;
for(int i = 1; i < n; ++i)
ans += max(0, min(left[i], right[i]) - height[i]);
return ans;
}
};

另一种写法:

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

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

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public int trap(int[] height) {
final int n = height.length;
if (n < 2) return 0;

int[] maxLeft = new int[n];
int[] maxRight = new int[n];
maxLeft[0] = height[0];
maxRight[n - 1] = height[n - 1];

for (int i = 1; i < n; i++)
maxLeft[i] = Math.max(maxLeft[i - 1], height[i]);
for (int i = n - 2; i >= 0; i--)
maxRight[i] = Math.max(maxRight[i + 1], height[i]);

int ans = 0;
for (int i = 1; i < n - 1; i++)
ans += Math.max(0, Math.min(maxLeft[i - 1], maxRight[i + 1]) - height[i]);
return ans;
}
}


 

但能用双指针做得更好:

两个指针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++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
int trap(vector<int>& height) {
int L = 0,R = height.size() - 1;
int max_left = 0,max_right = 0,ans = 0;
while(L < R){
if(height[L] <= height[R]){
max_left = max(max_left, height[L]);
ans += max_left - height[L++];
}
else{
max_right = max(max_right, height[R]);
ans += max_right - height[R--];
}
}
return ans;
}
};

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
def trap(self, height):
"""
:type height: List[int]
:rtype: int
"""
max_left = max_right = ans = 0
L, R = 0, len(height) - 1
while L < R:
if height[L] <= height[R]:
max_left = max(max_left, height[L])
ans += max_left - height[L]
L += 1
else:
max_right = max(max_right, height[R])
ans += max_right - height[R]
R -= 1
return ans

 

另一种写法:

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
int trap(vector<int>& height) {
int left = 0, right = height.size() - 1, left_max = 0, right_max = 0;
int ans = 0;
while(left <= right){
if(left_max < right_max){
if(left_max > height[left])
ans += left_max - height[left];
else
left_max = height[left];
++left;
}
else{
if(right_max > height[right])
ans += right_max - height[right];
else
right_max = height[right];
--right;
}
}
return ans;
}
};

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

请我喝杯咖啡吧~