【leetcode】42. 接雨水

daheww 2023-03-28 原文

题目

给定 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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/trapping-rain-water

题解

首先明确一个计算容积的方向——按照列来计算每个位置的容积，然后我们将每列的容积相加就得到整体的容积。将“示例1”中的容器按列划分，得到如上的图。
如何计算每个位置的容积呢？通过观察我们可以得出公式：位置i接水的容积 = Math.min([0,i)的最高位置, (i,length-1]的最高位置) - 位置i的高度。如下图所示：

示例1的接水容积计算过程如下图所示：

所以，我们可以维护两个数组：

第一个数组left[i]中存储的是[0,i]的最大值
第二个数组right[i]中存储的是[i,length -1]的最大值

然后再遍历一遍数组，使用公式：位置i接水的容积 = Math.min(left[i-1], right[i+1]) - 位置i的高度就能得到位置i的接水容积，最后将每个位置的接水容积相加就能得到总的容积。

代码如下：


class Solution {
    public int trap(int[] height) {
        // left[i]记录的是0～i位置上的最大值
        int[] left = new int[height.length];
        // right[i]记录的是i～0位置上的最大值
        int[] right = new int[height.length];

        // 1.初始化left[]
        int leftMax = 0;
        for (int i = 0; i < height.length; i++) {
            leftMax = Math.max(leftMax, height[i]);
            left[i] = leftMax;
        }

        // 2.初始化right[]
        int rightMax = 0;
        for (int i = height.length - 1; i >= 0; i--) {
            rightMax = Math.max(rightMax, height[i]);
            right[i] = rightMax;
        }

        // 3.计算容积
        int result = 0;
        for (int i = 1; i < height.length - 1; i++) {
            int v = Math.min(left[i - 1], right[i + 1]) - height[i];

            if (v > 0) {
                result += v;
            }
        }

        return result;
    }
}

leetcode 42 code 容积 height 算法与数据结构

有关【leetcode】42. 接雨水的更多相关文章

Python 刷Leetcode题库，顺带学英语单词（31） - 2
ValidPalindromeGivenastring,determineifitisapalindrome,consideringonlyalphanumericcharactersandignoringcases. [#125]Example:"Aman,aplan,acanal:Panama"isapalindrome."raceacar"isnotapalindrome.Haveyouconsiderthatthestringmightbeempty?Thisisagoodquestiontoaskduringaninterview.Forthepurposeofthisproblem
IDEA使用LeetCode插件 - 2
前言我们习惯用idea编写、调试代码，在LeetCode上刷题时，如果能够在IDEA编写代码，并且做好代码管理，是一件事半功倍的事情。对于后续复习题目，做笔记也会非常便利。本文目的在于介绍LeetCodeEditor的使用，以及配置工具类，最终目录结构如下：note：放置笔记src：放置代码leetcode.editor.cn：插件LeetCodeEditor自动生成utils：自定义的工具包，可用于自动化输入测试用例，定义题目需要的类（结构体）out：运行测试时自动生成LeetCodeEditorGitHub：https://github.com/shuzijun/leetcode-edit
ruby-on-rails - 在 El Capitan 上安装 Rails 时出现 -lgmp 错误的库未找到(Mac OS 10.11.1 (15B42)) - 2
在使用Rubyv2.2.2的ElCapitan(MacOSX10.11.1)上安装Rails时，出现以下错误:ERROR:Errorinstallingnokogiri:ERROR:Failedtobuildgemnativeextension./Users/jon/.rvm/rubies/ruby-2.2.2/bin/ruby-r./siteconf20151117-26799-ux15fd.rbextconf.rb--use-system-librariescheckingiftheCcompileraccepts...***extconf.rbfailed***Couldnotc
LeetCode——2347. 最好的扑克手牌 - 2
一、题目给你一个整数数组ranks和一个字符数组suit。你有5张扑克牌，第i张牌大小为ranks[i]，花色为suits[i]。下述是从好到坏你可能持有的手牌类型：“Flush”：同花，五张相同花色的扑克牌。“ThreeofaKind”：三条，有3张大小相同的扑克牌。“Pair”：对子，两张大小一样的扑克牌。“HighCard”：高牌，五张大小互不相同的扑克牌。请你返回一个字符串，表示给定的5张牌中，你能组成的最好手牌类型。注意：返回的字符串大小写需与题目描述相同。来源：力扣（LeetCode）链接：https://leetcode.cn/problems/best-poker-hand/d
LeetCode：344. 反转字符串 - 2
🍎道阻且长，行则将至。🍓🌻算法，不如说它是一种思考方式🍀算法专栏：👉🏻123一、🌱344.反转字符串题目描述：编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组s的形式给出。不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用O(1)的额外空间解决这一问题。来源：力扣（LeetCode）难度：简单提示：1s[i]都是ASCII码表中的可打印字符示例1：输入：s=[“h”,“e”,“l”,“l”,“o”]输出：[“o”,“l”,“l”,“e”,“h”]示例2：输入：s=[“H”,“a”,“n”,“n”,“a”,“h”]输出：[“h”,“a”,“n”,“n”,“a”,“H”
【日常系列】LeetCode《28·动态规划3》 - 2
数据规模->时间复杂度10^8内容二维数组中的路径问题买卖股票的最佳时机lc62【剑指098】【top100】：不同路径https://leetcode.cn/problems/unique-paths/提示：1题目数据保证答案小于等于2*10^9#方案一：dfs+记忆化classSolution:defuniquePaths(self,m:int,n:int)->int:memo=[[-1]*nfor_inrange(m)]defdfs(i,j):ifi==m-1andj==n-1:return1ifi>=morj>=n:return0ifmemo[i][j]!=-1:returnmemo[
javascript - 为什么 42.toString() 在 JS 中失败？ - 2
免责声明伙计们，我确实知道Whydoes10..toString()work,but10.toString()doesnot?问题存在，但问题是它没有提供正式的解释。Thespecification'sinterpretationofthe.characterinthatparticularpositionisthatitwillbeadecimal.ThisisdefinedbythenumericliteralsyntaxofECMAScript.不引用标准是不够可信的问题正文我下意识地明白了42..toString()被解析器视为42.数字，后跟.toString()调用。我不明
JavaScript:为什么 []+(-~{}-~{}-~{}-~{})+(-~{}-~{});返回 "42" - 2
在我的时事通讯中看到了这个。在Chrome和Firefox上测试。我还是想不通。[]+(-~{}-~{}-~{}-~{})+(-~{}-~{});//=>"42" 最佳答案评估:~{}使用内部函数求值:~ToInt32({})给出-1。引用ECMA规范-http://www.ecma-international.org/ecma-262/5.1/#sec-9.5这个解释-http://jibbering.com/faq/notes/type-conversion/#tcToInt32因此，在这种情况下(-~{}-~{})==2(-
LeetCode：454. 四数相加 II —— 哈希表为什么叫哈希表~ - 2
🍎道阻且长，行则将至。🍓🌻算法，不如说它是一种思考方式🍀算法专栏：👉🏻123hash是什么，哈希表为什么叫哈希表？一、🌱454.四数相加II题目描述：给你四个整数数组nums1、nums2、nums3和nums4，数组长度都是n，请你计算有多少个元组(i,j,k,l)能满足：0nums1[i]+nums2[j]+nums3[k]+nums4[l]==0来源：力扣（LeetCode）难度：中等提示：n==nums1.lengthn==nums2.lengthn==nums3.lengthn==nums4.length1-2^28示例1：输入：nums1=[1,2],nums2=[-2,-1],n
【树】你真的会二叉树了嘛? --二叉树LeetCode专题Ⅳ - 2
Halo，这里是Ppeua。平时主要更新C语言，C++，数据结构算法......感兴趣就关注我吧！你定不会失望。🌈个人主页：主页链接🌈算法专栏：专栏链接我会一直往里填充内容哒！🌈LeetCode专栏：专栏链接目前在刷初级算法的LeetBook。若每日一题当中有力所能及的题目，也会当天做完发出🌈代码仓库：Gitee链接🌈点击关注=收获更多优质内容🌈目录题目:111. 二叉树的最小深度题解:代码实现:题目:700. 二叉搜索树中的搜索题解:代码实现:题目:701. 二叉搜索树中的插入操作题解:代码实现:题目:450. 删除二叉搜索树中的节点题解:代码实现:完结撒花：人生苦短，

【leetcode】42. 接雨水

题目

题解

有关【leetcode】42. 接雨水的更多相关文章

随机推荐