LC 面试题 17.21. 直方图的水量

题目描述

这是 LeetCode 上的 面试题 17.21. 直方图的水量 ，难度为 困难。

给定一个直方图(也称柱状图)，假设有人从上面源源不断地倒水，最后直方图能存多少水量?直方图的宽度为 1。


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

示例:

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

输出: 6

朴素解法

对于每根柱子而言，我们只需要找出「其左边最高的柱子」和「其右边最高的柱子」。

对左右的最高柱子取一个最小值，再和当前柱子的高度做一个比较，即可得出当前位置可以接下的雨水。

同时，边缘的柱子不可能接到雨水（某一侧没有柱子）。

这样的做法属于「暴力做法」，但题目没有给数据范围，我们无法分析到底能否 AC。

唯唯诺诺交一个，过了 ~ （好题，建议加入蓝桥杯

代码：

[]
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) {
        int n = height.length;
        int ans = 0;
        for (int i = 1; i < n - 1; i++) {
            int cur = height[i];

            // 获取当前位置的左边最大值
            int l = Integer.MIN_VALUE;
            for (int j = i - 1; j >= 0; j--) l = Math.max(l, height[j]);
            if (l <= cur) continue;

            // 获取当前位置的右边边最大值
            int r = Integer.MIN_VALUE;
            for (int j = i + 1; j < n; j++) r = Math.max(r, height[j]);
            if (r <= cur) continue;

            // 计算当前位置可接的雨水
            ans += Math.min(l, r) - cur;
        }
        return ans;
    }
}

  • 时间复杂度：需要处理所有非边缘的柱子，复杂度为 $O(n)$；对于每根柱子而言，需要往两边扫描分别找到最大值，复杂度为 $O(n)$。整体复杂度为 $O(n^2)$。
  • 空间复杂度：$O(1)$。

预处理最值

朴素解法的思路有了，我们想想怎么优化。

事实上，任何的优化无非都是「减少重复」。

想想在朴素思路中有哪些环节比较耗时，耗时环节中又有哪些地方是重复的，可以优化的。

首先对每根柱子进行遍历，求解每根柱子可以接下多少雨水，这个 $O(n)$ 操作肯定省不了。

但在求解某根柱子可以接下多少雨水时，需要对两边进行扫描，求两侧的最大值。每一根柱子都进行这样的扫描操作，导致每个位置都被扫描了 $n$ 次。这个过程显然是可优化的。

换句话说：我们希望通过不重复遍历的方式找到任意位置的两侧最大值。

问题转化为：给定一个数组，如何求得任意位置的左半边的最大值和右半边的最大值。

一个很直观的方案是：直接将某个位置的两侧最大值存起来。

我们可以先从两端分别出发，预处理每个位置的「左右最值」，这样可以将我们「查找左右最值」的复杂度降到 $O(1)$。

整体算法的复杂度也从 $O(n^2)$ 下降到 $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
class Solution {
    public int trap(int[] height) {
        int n = height.length;
        int ans = 0;
        // 由于预处理最值的时候，我们会直接访问到 height[0] 或者 height[n - 1]，因此要特判一下
        if (n == 0) return ans;

        // 预处理每个位置左边的最值
        int[] lm = new int[n];
        lm[0] = height[0];
        for (int i = 1; i < n; i++) lm[i] = Math.max(height[i], lm[i - 1]);
        
        // 预处理每个位置右边的最值
        int[] rm = new int[n];
        rm[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i--) rm[i] = Math.max(height[i], rm[i + 1]);

        for (int i = 1; i < n - 1; i++) {
            ans += Math.min(lm[i], rm[i]) - height[i];
        }
        return ans;
    }
}

  • 时间复杂度：预处理出两个最大值数组，复杂度为 $O(n)$；计算每根柱子可接的雨水量，复杂度为 $O(n)$。整体复杂度为 $O(n)$。
  • 空间复杂度：使用了数组存储两侧最大值。复杂度为 $O(n)$。

单调栈

前面我们讲到，优化思路将问题转化为：给定一个数组，如何求得任意位置的左半边的最大值和右半边的最大值。

但仔细一想，其实我们并不需要找两侧最大值，只需要找到两侧最近的比当前位置高的柱子就行了。

针对这一类找最近值的问题，有一个通用解法：单调栈。

单调栈其实就是在栈的基础上，维持一个栈内元素单调。

在这道题，由于需要找某个位置两侧比其高的柱子（只有两侧有比当前位置高的柱子，当前位置才能接下雨水），我们可以维持栈内元素的单调递减。

PS. 找某侧最近一个比其大的值，使用单调栈维持栈内元素递减；找某侧最近一个比其小的值，使用单调栈维持栈内元素递增 …

当某个位置的元素弹出栈时，例如位置 a ，我们自然可以得到 a 位置两侧比 a 高的柱子：

  • 一个是导致 a 位置元素弹出的柱子（ a 右侧比 a 高的柱子）
  • 一个是 a 弹栈后的栈顶元素（a 左侧比 a 高的柱子）

当有了 a 左右两侧比 a 高的柱子后，便可计算 a 位置可接下的雨水量。

代码：

[]
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) {
        int n = height.length;
        int ans = 0;
        Deque<Integer> d = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            while (!d.isEmpty() && height[i] > height[d.peekLast()]) {
                int cur = d.pollLast();

                // 如果栈内没有元素，说明当前位置左边没有比其高的柱子，跳过
                if (d.isEmpty()) continue;

                // 左右位置，并有左右位置得出「宽度」和「高度」
                int l = d.peekLast(), r = i;
                int w = r - l + 1 - 2;
                int h = Math.min(height[l], height[r]) - height[cur];
                ans += w * h;
            }
            d.addLast(i);
        }
        return ans;
    }
}

  • 时间复杂度：每个元素最多进栈和出栈一次。复杂度为 $O(n)$。
  • 空间复杂度：栈最多存储 $n$ 个元素。复杂度为 $O(n)$。

面积差值

事实上，我们还能利用「面积差值」来进行求解。

我们先统计出「柱子面积」$sum$ 和「以柱子个数为宽、最高柱子高度为高的矩形面积」$full$。

然后分别「从左往右」和「从右往左」计算一次最大高度覆盖面积 $lSum$ 和 $rSum$。

显然会出现重复面积，并且重复面积只会独立地出现在「山峰」的左边和右边。

利用此特性，我们可以通过简单的等式关系求解出「雨水面积」：

image.png

代码：

[]
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
class Solution {
    public int trap(int[] height) {
        int n = height.length;

        int sum = 0, max = 0;
        for (int i = 0; i < n; i++) {
            int cur = height[i];
            sum += cur;
            max = Math.max(max, cur);
        }
        int full = max * n;

        int lSum = 0, lMax = 0;
        for (int i = 0; i < n; i++) {
            lMax = Math.max(lMax, height[i]);
            lSum += lMax;
        }

        int rSum = 0, rMax = 0;
        for (int i = n - 1; i >= 0; i--) {
            rMax = Math.max(rMax, height[i]);
            rSum += rMax;
        }

        return lSum + rSum - full - sum;
    }
}

  • 时间复杂度：$O(n)$。
  • 空间复杂度：$O(1)$。

最后

这是我们「刷穿 LeetCode」系列文章的第 No.面试题 17.21 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。