42. [H] Trapping Rain Water

https://leetcode.com/problems/trapping-rain-water/

扫描法

从左往右扫描,记录最近一次的最高点。累积水量是根据当前点和最近一次记录到的最高点的差额来计算,如果当前点较低则累计水量,否则则更新最高点的记录。

从左往右扫描,然后反方向从右往左再扫一次。注意,一次是遇到“更高点”的时候计算,一次是遇到“相等高度或更高点”的时候计算,这样避免等高点重复计算。

时间复杂度 O(n),空间复杂度 O(1)

// 1ms
class Solution {
public int trap(int[] height) {
int capacity = 0;
for (int i = 0, j = 0; i < height.length; i++) {
if (height[i] >= height[j]) {
for (int k = j; k < i; k++) {
capacity += height[j] - height[k];
}
j = i;
}
}
for (int i = height.length-1, j = height.length-1; i >= 0; i--) {
if (height[i] > height[j]) {
for (int k = j; k > i; k--) {
capacity += height[j] - height[k];
}
j = i;
}
}
return capacity;
}
}

两侧夹逼法

与前述思路类似,根据最近一次记录到的最高点计算累积水量。只是同时从两侧往中心夹逼计算。夹逼的最高点三种情况:

  • 最高点在最右侧

  • 最高点在最左侧

  • 最高点在中部

左右两侧必有一侧较低(或等高),始终移动较低的一侧,同时根据记录的左右最高点计算累计水量。

时间复杂度 O(n),空间复杂度 O(1)

// 0ms
class Solution {
public int trap(int[] height) {
if (height.length < 2) {
return 0;
}
int capacity = 0;
int l = 0, r = height.length-1;
int lx = height[l], rx=height[r];
while (l < r) {
if (height[l] < height[r]) {
if (height[l] > lx) {
lx = height[l];
} else {
capacity += lx - height[l];
}
l++;
} else {
if (height[r] > rx) {
rx = height[r];
} else {
capacity += rx - height[r];
}
r--;
}
}
return capacity;
}
}