【宫水三叶の真题精选】一题四解：朴素解法 & 预处理最值 & 单调栈 & 面积差

朴素解法

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

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

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

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

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

代码：

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

代码：

class Solution {
    public long maxWater(int[] height) {
        int n = height.length;
        long 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++) {
            int cur = height[i];

            int l = lm[i];
            if (l <= cur) continue;

            int r = rm[i];
            if (r <= cur) continue;

            ans += Math.min(l, r) - cur;
        }
        return ans;
    }
}

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

单调栈解法

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

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

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

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

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

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

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

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

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

代码：

import java.util.*;
class Solution {
    public long maxWater(int[] height) {
        int n = height.length;
        long 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;
                long 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$ 。

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

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

代码：

class Solution {
    public long maxWater(int[] height) {
        int n = height.length;

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

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

        long 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)$

最后

这是我们「必考真题の精选」系列文章的第 No. 篇，系列开始于 2021/07/01。

该系列会将牛客网中「题霸 - 面试必考真题」中比较经典而又不过时的题目都讲一遍。

在提供追求「证明」&「思路」的同时，提供最为简洁的代码。

欢迎关注，交个朋友 (｀・ω・´)