LeetCode 每日一题「接雨水」

陈皮的JavaLib

关注

发布于: 2021 年 06 月 14 日

我是陈皮，一个在互联网 Coding 的 ITer，微信搜索「陈皮的 JavaLib」第一时间阅读最新文章，回复【资料】，即可获得我精心整理的技术资料，电子书籍，一线大厂面试资料和优秀简历模板。

题目

给定 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 * 104
0 <= height[i] <= 105

题目来源：LeetCode

解法一

暴力法，我们可以将数组的每一个元素都看成一个桶，这样只要计算每一个桶的接水量，全部累加即可。那怎么知道每一个桶能接多少水呢？那只要计算这个桶两边的最大柱子高度，然后用两个最大高度的最小值，减去这个桶子的高度即这个桶能装的水量了。

暴力法虽简单，但是效率最低，因为每一个元素需要向前向后遍历，所以时间复杂度为 O(n^2)。空间复杂度为 O(1)。

package com.chenpi;
/** * @Description 接雨水 * @Author Mr.nobody * @Date 2021/6/14 * @Version 1.0 */public class TrappingRainWater {
    public static void main(String[] args) {        int[] height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};        TrappingRainWater tr = new TrappingRainWater();        System.out.println(tr.trap(height));    }

    public int trap(int[] height) {        // 存放雨水总量        int total = 0;        int size = height.length;        // 遍历每一个元素，计算每一个桶的装水量        for (int i = 1; i < size - 1; i++) {            // 从当前桶向左扫描，找出最高的柱子高度，包括自身高度            int maxLeft = 0;            for (int j = i; j >= 0; j--) {                maxLeft = Math.max(maxLeft, height[j]);            }            // 从当前桶向右扫描，找出最高的柱子高度，包括自身高度            int maxRight = 0;            for (int j = i; j < size; j++) {                maxRight = Math.max(maxRight, height[j]);            }            // 两个最高高度的最小值减去自身高度即当前桶的装水量            total += Math.min(maxLeft, maxRight) - height[i];        }        return total;    }}

复制代码

解法二

说到最值问题，我们最应该想到的是不是可以使用动态规划。在暴力法中，我们每计算一个桶的接水量的时候，需要计算桶子两边的最大柱子高度。那是否可以根据已经计算好的最大柱子高度，进而推算出下一个桶的两边最大柱子高度呢？动态规划算法可以做到。

从数组最左开始向右遍历，第一个元素的左最大高度肯定等于自身，那么后续每一个元素的左最大高度就等于前一个元素的左最大高度与当前元素的高度的最大值。
从数组最右开始向左遍历，第一个元素的右最大高度肯定等于自身，那么后续每一个元素的右最大高度就等于前一个元素的右最大高度与当前元素的高度的最大值。
最后，根据前两步骤的计算出来的两个最大高度数组，即可计算每一个元素的接水量。

需要遍历两次数组求出最左和最右最大高度，以及遍历最大高度数组求出总接水量，所以时间复杂度为 O(n)。空间复杂度为 O(n)。

package com.chenpi;
/** * @Description 接雨水 * @Author Mr.nobody * @Date 2021/6/14 * @Version 1.0 */public class TrappingRainWater {
    public static void main(String[] args) {        int[] height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};        TrappingRainWater tr = new TrappingRainWater();        System.out.println(tr.trap(height));    }
    public int trap(int[] height) {        if (null == height || height.length == 0) {            return 0;        }
        // 存放雨水总量        int total = 0;        int size = height.length;
        // 存放每一个元素的左最大高度        int[] leftMax = new int[size];        // 左边第一个元素的左最大高度肯定等于自身高度        leftMax[0] = height[0];        for (int i = 1; i < size; i++) {            // 每一个元素的左最大高度等于前一元素的左最大高度与当前元素的高度最大值            leftMax[i] = Math.max(height[i], leftMax[i - 1]);        }
        // 存放每一个元素的右最大高度        int[] rightMax = new int[size];        // 右边第一个元素的右最大高度肯定等于自身高度        rightMax[size - 1] = height[size - 1];        for (int i = size - 2; i >= 0; i--) {            // 每一个元素的右最大高度等于前一元素的右最大高度与当前元素的高度最大值            rightMax[i] = Math.max(height[i], rightMax[i + 1]);        }        for (int i = 1; i < size - 1; i++) {            // 计算每一个元素的接水量            total += Math.min(leftMax[i], rightMax[i]) - height[i];        }        return total;    }}