Leaky Cauldron
0%

接雨水问题

Posted on Edited on

题目(LeetCode #42)

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

题解

本题可转化为求每根柱子上可接到的水量的和, 而每根柱子上可留住的水量又取决于其左右两侧最高的柱子的高度, 假设一根柱子高度为 1, 其左右两侧最高的柱子高度为 3 和 5, 则这根柱子上方可留住的水量为 3 - 1 = 2.

预处理数组法

若每次迭代均遍历查找左右两侧的最大值将增加时间复杂度. 故可采用预处理数组的方式, 将数组中每个元素左右两侧的最大值保存起来. 本例中使用两个辅助数组, 分别保存每个位置上的左侧最大值和右侧最大值. 如下例所示:

1
2
3
[3, 2, 4, 5, 4, 3, 1] # 原数组
[3, 3, 4, 5, 5, 5, 5] # 每个元素左侧最大值构成的辅助数组
[5, 5, 5, 5, 4, 3, 1] # 每个元素右侧最大值构成的辅助数组

该种解法的时间复杂度和空间复杂度均为为 O(n)

Java

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
public class TrapRainWater {
    public static int trap(int[] heightArr) {
        if (heightArr == null || heightArr.length < 0)
            return 0;

        int arrLen = heightArr.length;
        int[] help1 = new int[arrLen];
        int[] help2 = new int[arrLen];
        int result = 0;

        help1[0] = heightArr[0];
        help2[arrLen - 1] = heightArr[arrLen - 1];

        for (int i = 1; i < arrLen; i++) {
            help1[i] = Math.max(help1[i - 1], heightArr[i]);
            help2[arrLen - i - 1] = Math.max(help2[arrLen - i], heightArr[arrLen - i - 1]);
        }

        for (int i = 1; i < arrLen - 1; i++) {
            int tmp = Math.min(help1[i - 1], help2[i + 1]) - heightArr[i];
            result += Math.max(tmp, 0);
        }

        return result;
    }

    public static void main(String[] args) {
        int[] heightArr = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        System.out.println(trap(heightArr));
    }
}
1
6

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class TrapRainWater:
    def trap(self, height_arr):
        if not height_arr or len(height_arr) < 0:
            return 0
        arr_len = len(height_arr)
        help1 = [0] * arr_len
        help2 = [0] * arr_len
        result = 0

        help1[0] = height_arr[0]
        help2[arr_len - 1] = height_arr[arr_len - 1]

        for i in range(1, arr_len):
            help1[i] = max(help1[i - 1], height_arr[i])
            help2[arr_len - i - 1] = max(help2[arr_len - i], height_arr[arr_len - i - 1])

        for i in range(1, arr_len - 1):
            tmp = min(help1[i - 1], help2[i + 1]) - height_arr[i]
            result += max(0, tmp)

        return result

Go

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
32
33
34
35
36
37
38
func trap(heightArr []int) int {
	if heightArr == nil || len(heightArr) < 0 {
		return 0
	}

	arrLen := len(heightArr)
	help1 := make([]int, arrLen)
	help2 := make([]int, arrLen)
	result := 0

	help1[0] = heightArr[0]
	help2[arrLen-1] = heightArr[arrLen-1]
	for i := 1; i < arrLen; i++ {
		help1[i] = max(help1[i-1], heightArr[i])
		help2[arrLen-i-1] = max(help2[arrLen-i], heightArr[arrLen-i-1])
	}

	for i := 1; i < arrLen-1; i++ {
		tmp := min(help1[i-1], help2[i+1])
		result += max(0, tmp-heightArr[i])
	}

	return result
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

双指针法

本方法时间复杂度为 O(N) 空间复杂度为 O(1)

Java

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
public class TrapRainWater {
    public static int trap(int[] heightArr) {
        if (heightArr == null || heightArr.length < 3)
            return 0;

        int arrLen = heightArr.length;
        int leftMax = heightArr[0];
        int rightMax = heightArr[arrLen - 1];
        int L = 1;
        int R = arrLen - 2;
        int result = 0;

        while (L <= R) {
            if (leftMax <= rightMax) {
                result += Math.max(0, leftMax - heightArr[L]);
                leftMax = Math.max(leftMax, heightArr[L++]);
            } else {
                result += Math.max(0, rightMax - heightArr[R]);
                rightMax = Math.max(rightMax, heightArr[R--]);
            }
        }

        return result;
    }
}

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class TrapRainWater:
    def trap(self, height_arr):
        if not height_arr or len(height_arr) < 3:
            return 0

        arr_len = len(height_arr)
        left_max = height_arr[0]
        right_max = height_arr[arr_len - 1]
        l = 1
        r = arr_len - 2
        result = 0

        while l <= r:
            if left_max <= right_max:
                result += max(0, left_max - height_arr[l])
                left_max = max(left_max, height_arr[l])
                l += 1
            else:
                result += max(0, right_max - height_arr[r])
                right_max = max(right_max, height_arr[r])
                r -= 1

        return result

Go

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
32
33
func trap(heightArr []int) int {
	if heightArr == nil || len(heightArr) < 3 {
		return 0
	}

	arrLen := len(heightArr)
	leftMax := heightArr[0]
	rightMax := heightArr[arrLen-1]
	L := 1
	R := arrLen - 2
	result := 0

	for L <= R {
		if leftMax <= rightMax {
			result += max(0, leftMax-heightArr[L])
			leftMax = max(leftMax, heightArr[L])
			L++
		} else {
			result += max(0, rightMax-heightArr[R])
			rightMax = max(rightMax, heightArr[R])
			R--
		}
	}

	return result
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}