【刷穿 LeetCode】42. 接雨水（困难）

宫水三叶的刷题日记

发布于 2021-02-20 09:48:16

6760

文章被收录于专栏：宫水三叶的刷题日记宫水三叶的刷题日记

题目描述

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

示例 1：

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

示例 2：

输入：height = [4,2,0,3,2,5]
输出：9

提示：

n == height.length
0 <= n <= 3 * 10^4
0 <= height[i] <= 10^5

朴素解法

观察示例图我们发现，对于每根柱子而言，我们只需要找出其左面的最高柱子和右面的最高柱子。

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

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

但是分析到这里你可能会想，每次都往左右找最大柱子。这样可是暴力方法啊。

这道题又是【困难】，会不会超时呢？

要是超时了，那不是白白浪费笔试/比赛的时间？

首先，朴素做法不代表不能 AC，「蓝桥杯」还有个「暴力杯」的戏称呢。

【困难】标签困难只是代表肯定有比朴素做法更好的优化方案。

具体超不超时还是要按照我最早在 【刷穿 LeetCode】4. 寻找两个正序数组的中位数 给你介绍的方法：

根据朴素解法的时空复杂度、给定的数据范围和计算机的理论执行时间进行判断。

这道题数据范围只有 30000 ，所以朴素做法稳稳的过，放心写。

代码：

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        if (n < 3) return 0;

        int ans = 0;
        for (int i = 1; i < n - 1; i++) {
            int cur = height[i];

            int left = 0;
            for (int j = i - 1; j >= 0; j--) 
                left = Math.max(left, height[j]);
            if (left <= cur) continue;

            int right = 0;
            for (int j = i + 1; j < n; j++) 
                right = Math.max(right, height[j]);
            if (right <= cur) continue;

            ans += Math.min(left, right) - cur;
        }
        return ans;
    }
}

时间复杂度：需要处理所有非边缘的柱子，复杂度为

O(n)

；对于每根柱子而言，需要往两边扫描分别找到最大值，复杂度为

O(n)

。整体复杂度为

O(n^2)

。

空间复杂度：

O(1)

最大值查找优化解法

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

一直看三叶的读者一定知道，任何的优化无非都是「减少重复」，这是三叶一直跟大家强调的优化出发点。

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

首先对每根柱子进行遍历，求解每根柱子可以接下多少雨水，这个

O(n)

操作肯定省不了。

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

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

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

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

我们可以从左往右遍历一次，将每一个位置的左侧（包括自身）的最大值存起来；同理，从右往左遍历，将每一个位置的右侧（包含自身）的最大值存起来。

这样我们通过一次遍历，就得到了每个位置的一侧的最大值，而不是对于每个位置的一侧最大值都进行一次遍历。

在求解每根柱子能接多少雨水时，通过访问数组就能知道当前位置的左侧最大值和右侧最大值，获取某侧最大值的复杂度从

O(n)

降到了

O(1)

。

代码：

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        if (n < 3) return 0;

        int[] leftCache = new int[n];
        leftCache[0] = height[0];
        for (int i = 1; i < n; i++) 
            leftCache[i] = Math.max(leftCache[i - 1], height[i]);

        int[] rightCache = new int[n];
        rightCache[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i--) 
            rightCache[i] = Math.max(rightCache[i + 1], height[i]);

        int ans = 0;
        for (int i = 1; i < n - 1; i++) {
            int cur = height[i];
            int left = leftCache[i - 1];
            int right = rightCache[i + 1];
            if (left <= cur || right <= cur) continue;
            ans += Math.min(left, right) - cur;
        }
        return ans;
    }
}

时间复杂度：预处理出两个最大值数组，复杂度为

O(n)

；计算每根柱子可接的雨水量，复杂度为

O(n)

。整体复杂度为

O(n)

。

空间复杂度：使用了数组存储两侧最大值。复杂度为

O(n)

单调栈解法

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

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

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

单调栈其实就是在栈「后进先出」的基础上，维持一个栈内元素单调。

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

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

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

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

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

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        if (n < 3) return 0;

        Deque<Integer> stack = new ArrayDeque<>();
        int ans = 0;
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && height[stack.peekLast()] < height[i]) {
                int idx = stack.pollLast();

                while (!stack.isEmpty() && height[stack.peekLast()] == height[idx]) 
                    stack.pollLast();
                    
                if (!stack.isEmpty()) {
                    int left = height[stack.peekLast()];
                    int right = height[i];
                    int val = Math.min(left, right) - height[idx];
                    int cnt = i - stack.peekLast() - 1;
                    ans += cnt * val;
                }
            }
            stack.addLast(i);
        }
        return ans;
    }
}

时间复杂度：每个元素最多进栈和出栈一次。复杂度为

O(n)

。

空间复杂度：栈最多存储 n 个元素。复杂度为

O(n)

对于 Java ，三叶使用了 Deque 双端队列来充当栈，而不是 Stack。

其中原因最早我在 【刷穿 LeetCode】20. 有效的括号（简单） 中跟你说过，主要是处于安全考虑。

最后

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

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

由于 LeetCode 的题目随着周赛 & 双周赛不断增加，为了方便我们统计进度，我们将按照系列起始时的总题数作为分母，完成的题目作为分子，进行进度计算。当前进度为 42/1916 。

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

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

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-02-02，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自宫水三叶的刷题日记微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度