Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.
给定n个非负整数表示每个宽度为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
26
27
28
29
30
31
| class Solution {
public int trap(int[] height) {
if (height == null || height.length == 0) {
return 0;
}
int left = 0, right = height.length - 1;
int leftMax = 0, rightMax = 0;
int trappedWater = 0;
while (left < right) {
if (height[left] < height[right]) {
if (height[left] >= leftMax) {
leftMax = height[left];
} else {
trappedWater += leftMax - height[left];
}
left++;
} else {
if (height[right] >= rightMax) {
rightMax = height[right];
} else {
trappedWater += rightMax - height[right];
}
right--;
}
}
return trappedWater;
}
}
|
双指针方式，空间复杂度O(1)，时间复杂度O(n)。
每次(x轴单位为1,递进1单位表示作一次比较)比较当前高度和历史最大高度的差形成雨槽。