leetcode-动态规划-42-接雨水
题目
给定 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
思路
这个问题可以使用双指针和动态规划的方法来解决,以下是使用双指针的解题思路:
-
我们可以通过遍历一遍数组来找出每个位置的左边最大高度和右边最大高度。
-
创建两个数组,
left_max
和right_max
,分别记录每个位置左边和右边的最大高度。 -
对于
left_max
数组,从左到右遍历数组,left_max[i]
表示位置i
左边的最大高度。 -
对于
right_max
数组,从右到左遍历数组,right_max[i]
表示位置i
右边的最大高度。 -
接下来,再次遍历数组,对于每个位置,计算其能接到的雨水量。雨水量可以通过取左右最大高度的较小值,减去当前位置的高度,来计算。
-
将每个位置的雨水量相加,就得到了总的雨水量。
这种解决方案的时间复杂度是O(n),其中n是数组的长度。
代码
object Solution {def trap(height: Array[Int]): Int = {val n = height.lengthif (n == 0) return 0var left = 0var right = n - 1var leftMax = 0var rightMax = 0var trappedWater = 0while (left < right) {if (height(left) < height(right)) {if (height(left) > leftMax) {leftMax = height(left)} else {trappedWater += leftMax - height(left)}left += 1} else {if (height(right) > rightMax) {rightMax = height(right)} else {trappedWater += rightMax - height(right)}right -= 1}}trappedWater}def main(args: Array[String]): Unit = {val height1 = Array(0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1)println(trap(height1)) // 输出 6val height2 = Array(4, 2, 0, 3, 2, 5)println(trap(height2)) // 输出 9}
}
相关文章:
leetcode-动态规划-42-接雨水
题目 给定 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…...
[静态时序分析简明教程(十一)]浅议tcl语言
静态时序分析简明教程-浅议tcl语言 一、写在前面1.1 快速导航链接 二、Tcl基础知识三、Tcl的语言结构3.1 Tcl变量3.2 Tcl表达式与运算符3.3 Tcl的控制流语句3.3.1 列表遍历3.3.2 决策3.3.3 Tcl循环3.3.4 Tcl过程 3.4 其他Tcl命令3.4.1 open/close3.4.2 gets/puts3.4.3 catch3.4…...
大数据-玩转数据-Flink 网站UV统计
一、说明 在实际应用中,我们往往会关注,到底有多少不同的用户访问了网站,所以另外一个统计流量的重要指标是网站的独立访客数(Unique Visitor,UV)。 二、数据准备 package com.lyh.flink06;import lombo…...
3分钟了解下cwnd和TCP拥塞控制算法
文章首发地址 cwnd是什么? cwnd是TCP拥塞控制中的一个重要概念,全称为“congestion window”,也被称为拥塞窗口。它用于限制发送方向网络发送数据的速度,以避免网络拥塞。cwnd是一个动态的值,可以根据网络状况动态调…...

设计模式之状态模式(State)的C++实现
1、状态模式的提出 在组件功能开发过程中,某些对象的状态经常面临变化,不同的状态,其对象的操作行为不同。比如根据状态写的if else条件情况,且这种条件变化是经常变化的,这样的代码不易维护。可以使用状态模式解决这…...

无涯教程-TensorFlow - Keras
Keras易于学习的高级Python库,可在TensorFlow框架上运行,它的重点是理解深度学习技术,如为神经网络创建层,以维护形状和数学细节的概念。框架的创建可以分为以下两种类型- 顺序API功能API 无涯教程将使用Jupyter Notebook执行和…...

使用SSH隧道将Ubuntu云服务器Jupyter Notebook端口映射到本地
本文主要实现了在Ubuntu云服务器后台运行Jupyter Notebook,并使用SSH隧道将服务器端口映射到本地 1. 生成配置文件 运行以下命令生成Jupyter Notebook的配置文件: jupyter notebook --generate-config这将在用户主目录下生成一个名为.jupyter的文件夹&…...
Keepalived+LVS部署高可用集群
文章目录 KeepalivedLVS(DR)部署高可用Web集群集群环境MASTER配置BACKUP配置检查Virtual IP是否漂移IPVS检查MASTERBACKUP Real Server配置附上个人写的小脚本 测试停用Real Server某一台的Apache服务停用Master上的keepalived检测Backup是否接管资源 KeepalivedLVS(DR)部署高可…...

2023河南萌新联赛第(五)场:郑州轻工业大学
A.买爱心气球 原题链接 : 登录—专业IT笔试面试备考平台_牛客网 博弈论 : #include <iostream> using namespace std; int t,n,m; string s1 "Alice",s2 "Bob"; int main() {cin>>t;while(t--){cin>>n>>m;if (n % 3 0) {cou…...

在Orangepi5开发板3588s使用opencv获取摄像头画面
先感谢香橙派群的管理员耐心指导,经过不断的调试修改最后成功通过opencv调用mipi摄像头获取画面 就记录分享一下大概步骤希望大家少踩点坑!!!!!! 我用的固件系统是ubuntu2022.0.4 固件是&#x…...
音视频 ffmpeg命令分类查询
命令参数内容-version显示版本 -bsfs 显示可用比特流filter-buildconf显示编译配置-formats显示可用格式(muxersdemuxers)-muxers显示可用复用器-demuxers显示可用解复用器-codecs显示可用编解码器(decodersencoders)-decoders显示可用解码器-encoders显示可用编码器-bsfs显示可…...

VSCode无法从Extensions下载工具时,把工具下载到本地并添加到VSCode编辑器
从VSCode 的 Extensions 下载 下载报错:Error while installing ...... extension. Please check the log for more details. 由于内网限制(或者其他网络限制)无法正常下载扩展工具到VSCode编辑器,可以把工具下载到本地再添加到V…...

WebStrom 前端项目Debug
1. 正常启动前端项目 2. 配置webStrom的JavaScript Debugger 点击Edit Configurations添加avaScript Debug填写URL 为项目启动路径配置要Debug的浏览器-remote-allow-origins* (最重要,否则唤起的是一个about:blank空白页面) 3. 启动Debug模…...

【ARM Linux 系统稳定性分析入门及渐进12 -- GDB内存查看命令 “x“(examine)】
文章目录 gdb 内存查看命令 examine 上篇文章:ARM Linux 系统稳定性分析入门及渐进11 – GDB( print 和 p 的使用| 和 ::的使用|ptype|{<type>} <addr> ) gdb 内存查看命令 examine examine是…...
kube-prometheus 系列1 项目介绍
Prometheus 已经成为云原生监控的事实标准。整个生态包含诸多组件,为了简化安装部署和配置高可用等,社区开发了kube-prometheus项目。接下来用一系列文章介绍一下相关配置。 项目简介: kube-prometheus 是一个基于 Kubernetes 部署的 Prometh…...
深度学习在组织病理学图像分析中的应用: Python实现和代码解析
引言 组织病理学是医学的一个重要分支,它主要研究组织和细胞的形态学改变,以确定疾病的性质和发展。随着深度学习技术的进步,其在组织病理学图像分析中的应用也变得日益重要。本文旨在介绍如何使用Python和深度学习技术来处理和分析组织病理…...
kotlin的列表
在 kotlin中,列表是一种常见的数据结构,用于存储有序的元素集合。 kotlin的标准库提供了 List 接口及其实现类 ArrayList、LinkedList 等,以及一些扩展函数来操作和处理列表。 1.创建列表 // 创建一个可变列表 val mutableList mutableLis…...

PCL 三维点云边界提取(C++详细过程版)
边界提取 一、概述二、代码实现三、结果展示本文由CSDN点云侠原创,爬虫自重。如果你不是在点云侠的博客中看到该文章,那么此处便是不要脸的爬虫。 一、概述 点云边界提取在PCL里有现成的调用函数,具体算法原理和实现代码见:PCL 点云边界提取。为充分了解pcl::BoundaryEsti…...

../../ 目录遍历
在web功能设计中,很多时候我们会要将需要访问的文件定义成变量,从而让前端的功能便的更加灵活。 当用户发起一个前端的请求时,便会将请求的这个文件的值(比如文件名称)传递到后台,后台再执行其对应的文件。 在这个过程中,如果后…...
clickhouse集群部署
一、集群部署简介 部署的详情可以看官网 先部署两个server,三个keeper[zookeeper] clickhouse之前依赖的存储是zookeeper,后来改为了keeper,官网给出了原因 所以这就决定了clickhouse有两种安装方式,依赖于keeper做存储或者依赖于zookeeper做存储 二、zookeeper作…...
KubeSphere 容器平台高可用:环境搭建与可视化操作指南
Linux_k8s篇 欢迎来到Linux的世界,看笔记好好学多敲多打,每个人都是大神! 题目:KubeSphere 容器平台高可用:环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...

未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?
编辑:陈萍萍的公主一点人工一点智能 未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战,在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...

第19节 Node.js Express 框架
Express 是一个为Node.js设计的web开发框架,它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用,和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...

Unity3D中Gfx.WaitForPresent优化方案
前言 在Unity中,Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染(即CPU被阻塞),这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案: 对惹,这里有一个游戏开发交流小组&…...
DockerHub与私有镜像仓库在容器化中的应用与管理
哈喽,大家好,我是左手python! Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库,用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...

【Java_EE】Spring MVC
目录 Spring Web MVC 编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 编辑参数重命名 RequestParam 编辑编辑传递集合 RequestParam 传递JSON数据 编辑RequestBody …...
拉力测试cuda pytorch 把 4070显卡拉满
import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试,通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小,增大可提高计算复杂度duration: 测试持续时间(秒&…...

微信小程序云开发平台MySQL的连接方式
注:微信小程序云开发平台指的是腾讯云开发 先给结论:微信小程序云开发平台的MySQL,无法通过获取数据库连接信息的方式进行连接,连接只能通过云开发的SDK连接,具体要参考官方文档: 为什么? 因为…...
Unit 1 深度强化学习简介
Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库,例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体,比如 SnowballFight、Huggy the Do…...