LeetCode 42:接雨水

2024-01-07 21:16:31

一、题目描述

给定?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
  • 1 <= n <= 2 * 104
  • 0 <= height[i] <= 105

二、思路分析

本题的解法有很多,这里使用动态规划进行解答。首先,动态规划是:通过将原问题分解为相对简单的子问题的方式求解复杂问题的方法。

根据本题题意,我们需要找到存在凹槽的地方,这样才能够积攒雨水。首先创建两个数组,maxLeft [i] 代表第 i 列左边最高的墙的高度,maxRight [i] 代表第 i 列右边最高的墙的高度。(要注意下,第 i 列左(右)边最高的墙,是不包括自身的)

对于 maxLeft 我们可以这样求:

maxLeft[i] = Math.max(maxLeft[i - 1], height[i - 1]); 它前边的墙的左边的最高高度和它前边的墙的高度选一个较大的,就是当前列左边最高的墙了。

对于 maxRight 我们可以这样求:

maxRight[i] = Math.max(maxRight[i + 1], height[i + 1]); 它后边的墙的右边的最高高度和它后边的墙的高度选一个较大的,就是当前列右边最高的墙了。

三、代码参考

1、Java

class Solution {
    public int trap(int[] height) {
        // 用来计算最终结果,初始值为 0
        int sum = 0;
        // 创建数组 maxLeft,用来表示第 i 列左边最高的墙
        int[] maxLeft = new int[height.length];
        // 创建数组 maxRight,用来表示第 i 列右边最高的墙
        int[] maxRight = new int[height.length];
        // 循环遍历,获得数组中每一列左边最高的墙
        for(int i = 1; i < height.length; i++){
            // 获得第 i 列左边最高的墙
            maxLeft[i] = Math.max(maxLeft[i - 1], height[i - 1]);
        }
        // 循环遍历,获得数组中每一列右边最高的墙
        for(int i = height.length - 2; i >= 0; i--){
            // 获取第 i 列右边最高的墙
            maxRight[i] = Math.max(maxRight[i + 1], height[i + 1]);
        }
        // 通过 maxLeft 和 maxRight 两个数组来获取第 i 列左右两边的墙谁最矮,因为凹槽的积水面积的高度取决于矮的一边
        for(int i = 1; i < height.length; i++){
            // 获取第 i 列左右两边墙高度最小的值
            int min = Math.min(maxLeft[i], maxRight[i]);
            // 如果有凹槽,即当前列的高度小于列左右两边最小的高度
            if(min > height[i]){
                // 计算当前列的积水面积,并汇总
                sum = sum + (min - height[i]);
            }
        }
        // 返回结果
        return sum;
    }
}

文章来源:https://blog.csdn.net/Jarvs/article/details/135414134
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。