LeetCode42-接雨水

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/trapping-rain-water/

中文链接：https://leetcode-cn.com/problems/trapping-rain-water/

题目详述

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

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

示例:

1
2
输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

题目详解

方法一：单调栈。

  • 保持栈底到栈顶单调递减。
  • 遍历数组，如果当前元素大于等于栈顶元素 ，弹出栈顶元素进行结算。
  • 时间复杂度为 O(n)，空间复杂度为 O(n)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class LeetCode_00042 {

    public int trap(int[] height) {
        int res = 0;
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < height.length; ++i) {
            while (!stack.isEmpty() && height[i] >= height[stack.peek()]) {
                int cur = stack.pop();
                if (!stack.isEmpty()) {
                    int pre = stack.peek();
                    res += (Math.min(height[pre], height[i]) - height[cur]) * (i - 1 - pre);
                }
            }
            stack.push(i);
        }
        return res;
    }
}

方法二：双指针。

  • 对于数组中的每个元素，它接的雨水量等于它左右两边最大高度的较小值减去当前高度的值。
  • 对于每个元素，它左右两边最大高度可以提前算出来。
  • 然后遍历数组，记录每个位置的雨水贡献量，累加即可。
  • 时间复杂度为 O(n)，空间复杂度为 O(n)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class LeetCode_00042 {

    public int trap(int[] height) {
        if (height == null || height.length < 3) {
            return 0;
        }
        int n = height.length;
        int[] leftMax = new int[n];
        int[] rightMax = new int[n];
        leftMax[0] = height[0];
        for (int i = 1; i < n; ++i) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i]);
        }
        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; --i) {
            rightMax[i] = Math.max(rightMax[i + 1], height[i]);
        }
        int res = 0;
        for (int i = 1; i < n - 1; ++i) {
            res += Math.min(leftMax[i], rightMax[i]) - height[i];
        }
        return res;
    }
}
  • 对上面的代码进行优化，可以不用找到当前位置左右两边的最大值再取较小值（短板），知道谁是短板后可以直接结算，因为接水量取决于短板，即便中间还有没有走过的位置，此时接水量已经确定了。
  • 记短板高度为 s，当前高度为 c，如果 s > c，则当前接水量为 s - c；否则为 0。
  • 运用两个指针从两端往中间扫描，结算每个位置的雨水贡献量，累加即可。
  • 时间复杂度为 O(n)，空间复杂度为 O(1)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class LeetCode_00042 {

    public int trap(int[] height) {
        if (height == null || height.length < 3) {
            return 0;
        }
        int res = 0;
        int i = 0, j = height.length - 1;
        int leftMax = 0, rightMax = 0;
        while (i < j) {
            if (height[i] < height[j]) {
                leftMax = Math.max(leftMax, height[i]);
                res += leftMax - height[i++];
            } else {
                rightMax = Math.max(rightMax, height[j]);
                res += rightMax - height[j--];
            }
        }
        return res;
    }
}

LeetCode11-盛最多水的容器 也是类似的思想，运用双指针进行扫描，不过结算的方式不同。