LeetCode - 42 接雨水
目录
题目来源
题目描述
示例
提示
题目解析
算法源码
题目来源
42. 接雨水 - 力扣(LeetCode)
题目描述
给定 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 * 10^4
- 0 <= height[i] <= 10^5
题目解析
本题要计算所有柱子的储水量之和,而这个和其实可以分解求解每一个柱子的储水量。
而一个柱子要想储存住水,则必然在其左边有一根高柱,在其右边也有一根高柱,因为这样才能形成“凹”,才能在中间的低柱子上存储住水。
并且,中间低柱子的储水量取决于,其左边“最高的”柱子,和其右边“最高的”柱子的较矮者,比如下图中:

绿色箭头指向的低柱子的储水量取决于:其左边最高柱子,和其右边最高柱子的较矮者。
因此,本题其实是要我们求解每一根柱子的:
- 左边最高柱子高度
- 右边最高柱子高度
这个求解,可以使用动态规划来做:
我们假设第 i 根柱子的高度为 h[i],第 i 根柱子的左边最高柱子高度表示为left[ i ]
则第 i 根柱子的左边的最高柱子高度为:
left[ i ] = max( left[ i - 1 ], h[ i - 1 ] )
什么含义呢?
第 i 根柱子左边的最高柱子:
- 要么是 第 i - 1 根柱子,即h[ i - 1 ]
- 要么是 第 i - 1 根柱子的左边的最高柱子,即 left[ i - 1 ]
我们只要从左到右完成left数组的初始化即可。
同理,可得:
right[ i ] = max( right[ i + 1 ], h[ i + 1 ] )
此时需要从右往左完成right数组的初始化。
这样的话,第 i 根柱子的储水量
取决于其左边最高柱子,和其右边最高柱子的较矮者,即min(left[ i ], right[ i ])
第 i 根柱子的储水量val = min(left[ i ], right[ i ]) - h[ i ]
注意val最小为0,不能为负数。因此最终第 i 根柱子的储水量计算公式为:
max(0, min(left[ i ], right[ i ]) - h[i])
我们只要累加每根柱子的储水量即为题解。
Java算法源码
class Solution {public int trap(int[] h) {int n = h.length;// left[i] 表示 第 i 根柱子的左边的最高的柱子的高度int[] left = new int[n];for(int i=1; i<n; i++) {// 第 i 根柱子左边最高的柱子要么是h[i-1],即第i-1根柱子的高度,要么是left[i-1],即第i-1根柱子的左边的最高的柱子的高度left[i] = Math.max(left[i-1], h[i-1]);}// right[i] 表示 第 i 根柱子的右边的最高的柱子的高度int[] right = new int[n];for(int i=n-2; i>=0; i--) {// 第 i 根柱子右边最高的柱子要么是h[i+1],即第i+1根柱子的高度,要么是right[i+1],即第i+1根柱子的右边的最高的柱子的高度right[i] = Math.max(right[i+1], h[i+1]);}int ans = 0;for(int i=1; i<n-1; i++) {// 第i根柱子最多能蓄水的量,取决于其左边最高的柱子和右边最高的柱子的较矮的那个,且较矮的那根柱子 - 第i根柱子的高度就是第i根柱子的蓄水量,注意蓄水量最少为0ans += Math.max(0, Math.min(left[i], right[i]) - h[i]);}return ans;}
}

JS算法源码
/*** @param {number[]} height* @return {number}*/
var trap = function(h) {const n = h.length// left[i] 表示 第 i 根柱子的左边的最高的柱子的高度const left = new Array(n).fill(0)for(let i=1; i<n; i++) {// 第 i 根柱子左边最高的柱子要么是h[i-1],即第i-1根柱子的高度,要么是left[i-1],即第i-1根柱子的左边的最高的柱子的高度left[i] = Math.max(left[i-1], h[i-1])}// right[i] 表示 第 i 根柱子的右边的最高的柱子的高度const right = new Array(n).fill(0)for(let i=n-2; i>=0; i--) {// 第 i 根柱子右边最高的柱子要么是h[i+1],即第i+1根柱子的高度,要么是right[i+1],即第i+1根柱子的右边的最高的柱子的高度right[i] = Math.max(right[i+1], h[i+1])}let ans = 0for(let i=1; i<n-1; i++) {// 第i根柱子最多能蓄水的量,取决于其左边最高的柱子和右边最高的柱子的较矮的那个,且较矮的那根柱子 - 第i根柱子的高度就是第i根柱子的蓄水量,注意蓄水量最少为0ans += Math.max(0, Math.min(left[i], right[i]) - h[i])}return ans
};

Python算法源码
class Solution(object):def trap(self, h):""":type height: List[int]:rtype: int"""n = len(h)# left[i] 表示 第 i 根柱子的左边的最高的柱子的高度left = [0]*nfor i in range(1, n):# 第 i 根柱子左边最高的柱子要么是h[i-1],即第i-1根柱子的高度,要么是left[i-1],即第i-1根柱子的左边的最高的柱子的高度left[i] = max(left[i-1], h[i-1])# right[i] 表示 第 i 根柱子的右边的最高的柱子的高度right = [0]*nfor i in range(n-2,0,-1):# 第 i 根柱子右边最高的柱子要么是h[i+1],即第i+1根柱子的高度,要么是right[i+1],即第i+1根柱子的右边的最高的柱子的高度right[i] = max(right[i+1], h[i+1])ans = 0for i in range(1, n-1):# 第i根柱子最多能蓄水的量,取决于其左边最高的柱子和右边最高的柱子的较矮的那个,且较矮的那根柱子 - 第i根柱子的高度就是第i根柱子的蓄水量,注意蓄水量最少为0ans += max(0, min(left[i], right[i]) - h[i])return ans

相关文章:
LeetCode - 42 接雨水
目录 题目来源 题目描述 示例 提示 题目解析 算法源码 题目来源 42. 接雨水 - 力扣(LeetCode) 题目描述 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。 示例1 输入&…...
python --生成时间序列,作为横轴的标签。时间跨越2008-2022年,生成每年的6-10月的第一天作为时间序列
python 生成制定的时间序列作为绘图时x轴的标签 问题需求 在绘图时,需要对于x轴的标签进行专门的设置,整体时间跨越2008年-2022年,将每年的6-10月的第一天生成一条时间序列,绘制成图。 解决思路 对于时间序列的生成࿰…...
【Unity VR开发】结合VRTK4.0:创建一个按钮(Togglr Button)
语录: 有人感激过你的善良吗,貌似他们只会得寸进尺。 前言: Toggle按钮是提供简单空间 UI 选项的另一种方式,在该选项中,按钮将保持其状态,直到再次单击它。这允许按钮处于激活状态或停用状态的情况&#…...
lottie-miniprogram在taro+vue的小程序中怎么使用
把一个json的动图展示在页面上。使用的是插件lottie-miniprogramhttps://blog.csdn.net/qq_33769914/article/details/128705922之前介绍过。但是发现使用在taro使用的时候他会报错。那可能是因为我们 wx.createSelectorQuery().select(#canvas).node(res > {console.log(re…...
C++回顾(二十二)—— stack容器 与 queue容器
22.1 stack容器 (1) stack容器简介 stack是堆栈容器,是一种“先进后出”的容器。stack是简单地装饰deque容器而成为另外的一种容器。添加头文件:#include <stack> (2)stack对象的默认构造 stack…...
逻辑优化基础-disjoint support decomposition
先遣兵 在了解 disjoint support decomposition 之前,先学习两个基本的概念。 disjoint 数学含义上的两个集合交集,所谓非相交,即交集为空集。 A∩BC⊘A \cap B C \oslash A∩BC⊘ support 逻辑综合中的 supportsupportsupport 概念是…...
保姆级使用PyTorch训练与评估自己的DaViT网络教程
文章目录前言0. 环境搭建&快速开始1. 数据集制作1.1 标签文件制作1.2 数据集划分1.3 数据集信息文件制作2. 修改参数文件3. 训练4. 评估5. 其他教程前言 项目地址:https://github.com/Fafa-DL/Awesome-Backbones 操作教程:https://www.bilibili.co…...
Java8新特性:Stream流处理使用总结
一. 概述 Stream流是Java8推出的、批量处理数据集合的新特性,在java.util.stream包下。结合着Java8同期推出的另一项新技术:行为参数化(包括函数式接口、Lambda表达式、方法引用等),Java语言吸收了函数式编程的语法特…...
Java基准测试工具JMH高级使用
去年,我们写过一篇关于JMH的入门使用的文章:Java基准测试工具JMH使用,今天我们再来聊一下关于JMH的高阶使用。主要我们会围绕着以下几点来讲: 对称并发测试非对称并发测试阻塞并发测试Map并发测试 关键词 State 在很多时候我们…...
问心 | 再看token、session和cookie
什么是cookie HTTP Cookie(也叫 Web Cookie或浏览器 Cookie)是服务器发送到用户浏览器并保存在本地的一小块数据,它会在浏览器下次向同一服务器再发起请求时被携带并发送到服务器上。 什么是session Session 代表着服务器和客户端一次会话…...
Ubuntu 安装 CUDA and Cudnn
文章目录0 查看 nvidia驱动版本1 下载Cuda2 下载cudnn参考:0 查看 nvidia驱动版本 nvidia-smi1 下载Cuda 安装之前先安装 gcc g gdb 官方:https://developer.nvidia.com/cuda-toolkit-archive,与驱动版本进行对应,我这里是12.0…...
【漏洞复现】Grafana任意文件读取(CVE-2021-43798)
docker环境搭建 #进入环境 cd vulhub/grafana/CVE-2021-43798#启动环境,这个过程可能会有点慢,保持网络通畅 docker-compose up -d#查看环境 docker-compose ps直接访问虚拟机 IP地址:3000 目录遍历原理 目录遍历原理:攻击者可以通过将包含…...
磨金石教育摄影技能干货分享|春之旅拍
春天来一次短暂的旅行,你会选择哪里呢?春天的照片又该如何拍呢?看看下面的照片,或许能给你答案。照片的构图很巧妙,画面被分成两部分,一半湖泊,一半绿色树林。分开这些的是一条斜向的公路&#…...
中断以及 PIC可编程中断控制器
1 中断分为同步中断(中断)和异步中断(异常) 1.1 中断和异常的不同 中断由IO设备和定时器产生,用户的一次按键会引起中断。异步。 异常一般由程序错误产生或者由内核必须处理的异常条件产生。同步。缺页异常ÿ…...
SecureCRT 安装并绑定ENSP设备终端
软件下载链接链接:https://pan.baidu.com/s/1WFxmQgaO9bIiUTwBLSR4OA?pwd2023 提取码:2023 CRT安装:软件可以从上面链接进行下载,下载完成后解压如下:首先双击运行scrt-x64.8.5.4 软件,进行安装点击NEXT选…...
ESP32设备驱动-TCS3200颜色传感器驱动
TCS3200颜色传感器驱动 1、TCS3200介绍 TCS3200 和 TCS3210 可编程彩色光频率转换器在单个单片 CMOS 集成电路上结合了可配置的硅光电二极管和电流频率转换器。 输出是方波(50% 占空比),其频率与光强度(辐照度)成正比。 满量程输出频率可以通过两个控制输入引脚按三个预…...
< JavaScript小技巧:Array构造函数妙用 >
文章目录👉 Array构造函数 - 基本概念👉 Array函数技巧用法1. Array.of()2. Array.from()3. Array.reduce()4. (Array | String).includes()5. Array.at()6. Array.flat()7. Array.findIndex()📃 参考文献往期内容 💨今天这篇文章…...
【17】组合逻辑 - VL17/VL19/VL20 用3-8译码器 或 4选1多路选择器 实现逻辑函数
VL17 用3-8译码器实现全减器 【本题我的也是绝境】 因为把握到了题目的本质要求【用3-8译码器】来实现全减器。 其实我对全减器也是不大清楚,但是仿照对全加器的理解,全减器就是低位不够减来自低位的借位 和 本单元位不够减向后面一位索要的借位。如此而已,也没有很难理解…...
2023年全国最新二级建造师精选真题及答案19
百分百题库提供二级建造师考试试题、二建考试预测题、二级建造师考试真题、二建证考试题库等,提供在线做题刷题,在线模拟考试,助你考试轻松过关。 37.下列纠纷中,属于劳动争议范围的有()。 A.因劳动保护发生的纠纷 B.家庭与家政…...
Java中的 this 和 super
1 this 关键字 1.1 this 访问本类属性 this 代表对当前对象的一个引用 所谓当前对象,指的是调用当前类中方法或属性的那个对象this只能在方法内部使用,表示对“调用方法的那个对象”的引用this.属性名,表示本对象自己的属性 当对象的属性和…...
7.4.分块查找
一.分块查找的算法思想: 1.实例: 以上述图片的顺序表为例, 该顺序表的数据元素从整体来看是乱序的,但如果把这些数据元素分成一块一块的小区间, 第一个区间[0,1]索引上的数据元素都是小于等于10的, 第二…...
AtCoder 第409场初级竞赛 A~E题解
A Conflict 【题目链接】 原题链接:A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串,只有在同时为 o 时输出 Yes 并结束程序,否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...
Opencv中的addweighted函数
一.addweighted函数作用 addweighted()是OpenCV库中用于图像处理的函数,主要功能是将两个输入图像(尺寸和类型相同)按照指定的权重进行加权叠加(图像融合),并添加一个标量值&#x…...
Unit 1 深度强化学习简介
Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库,例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体,比如 SnowballFight、Huggy the Do…...
第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词
Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵,其中每行,每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid,其中有多少个 3 3 的 “幻方” 子矩阵&am…...
AspectJ 在 Android 中的完整使用指南
一、环境配置(Gradle 7.0 适配) 1. 项目级 build.gradle // 注意:沪江插件已停更,推荐官方兼容方案 buildscript {dependencies {classpath org.aspectj:aspectjtools:1.9.9.1 // AspectJ 工具} } 2. 模块级 build.gradle plu…...
代码随想录刷题day30
1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...
JVM 内存结构 详解
内存结构 运行时数据区: Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器: 线程私有,程序控制流的指示器,分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 每个线程都有一个程序计数…...
GruntJS-前端自动化任务运行器从入门到实战
Grunt 完全指南:从入门到实战 一、Grunt 是什么? Grunt是一个基于 Node.js 的前端自动化任务运行器,主要用于自动化执行项目开发中重复性高的任务,例如文件压缩、代码编译、语法检查、单元测试、文件合并等。通过配置简洁的任务…...
Java求职者面试指南:Spring、Spring Boot、Spring MVC与MyBatis技术解析
Java求职者面试指南:Spring、Spring Boot、Spring MVC与MyBatis技术解析 一、第一轮基础概念问题 1. Spring框架的核心容器是什么?它的作用是什么? Spring框架的核心容器是IoC(控制反转)容器。它的主要作用是管理对…...
