力扣热门100题之接雨水【困难】
题目描述
给定 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](https://img-blog.csdnimg.cn/2ff2181278424d74bc4d14e6cdc0c065.png)
解法1 按列计算
/*** @param {number[]} height* @return {number}*/
var trap = function(height) {let area=0;let leftMax=0;let rightMax=0;for(let i=0;i<height.length;i++){rightMax=findRightMax(leftMax,i,height);if(height[i]<leftMax&&rightMax>height[i]){area+=Math.min(leftMax,rightMax)-height[i];}else if(!findRightMax(leftMax,i,height)){leftMax=height[i];}if(height[i]>leftMax) leftMax=height[i];}return area;
};
function findRightMax(num,j,height){let n=0;for(let i=j;i<height.length;i++){if(height[i]>=num){return height[i];}if(height[i]>n)n=height[i]}return n;
}
执行结果:

解法2:双指针解法【注意理解】
/*** @param {number[]} height* @return {number}*/
var trap = function(height) {let area=0;if(height.length<=1) return 0;let left=0;let leftMax=0;let right=height.length-1;let rightMax=0;while(left<right){leftMax=Math.max(leftMax,height[left]);rightMax=Math.max(rightMax,height[right]);if(height[left]<height[right]){area+=leftMax-height[left];left++;}else{area+=rightMax-height[right];right--;}}return area;
};
执行情况:

解法3:单调栈【参照力扣官方】
/*** @param {number[]} height* @return {number}*/
var trap = function(height) {let area=0;if(height.length<=1) return 0;const stack=[]//存值值单调递减的下标for(let i=0;i<height.length;i++){while(stack.length&&height[i]>height[stack[stack.length-1]]){let top=stack.pop();if(stack.length==0){break;}const left = stack[stack.length - 1];const currWidth = i - left - 1;const currHeight = Math.min(height[left], height[i]) - height[top];area += currWidth * currHeight;}stack.push(i);}return area;
};

相关文章:
力扣热门100题之接雨水【困难】
题目描述 给定 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…...
Stable-Diffusion-Webui部署SDXL0.9报错参数shape不匹配解决
问题 已经在model/stable-diffusion文件夹下放进去了sdxl0.9的safetensor文件,但是在切换model的时候,会报错model的shape不一致。 解决方法 git pullupdate一些web-ui项目就可以,因为当前项目太老了,没有使用最新的版本。...
Springboot @Async 多线程获取返回值
Springboot Async 多线程获取返回值 需求背景 最近需要用到多线程, 自己维护线程池很麻烦, 正好看到Springboot集成线程池的例子, 这里自己做了个尝试和总结, 记录一下, 也分享给需要的朋友; 不考虑事务的情况下, 这个多线程实现比较简单, 主要有以下几点: 在启动类加上Enab…...
怎样接入chatGPT
官网链接: OpenAI platform...
Docker consul容器服务更新与发现
Docker consul容器服务更新与发现 一、什么事服务注册与发现二、什么是consul三、consul部署1、consul服务器2、registrator服务器3、consul-template 一、什么事服务注册与发现 服务注册与发现是微服务架构中不可或缺的重要组件。起初服务都是单节点的,不保障高可…...
[算法很美打卡] 多维数组篇 (打卡第一天)
文章目录 顺时针打印二维数组0所在的行列清零 顺时针打印二维数组 package 每日算法学习打卡.算法打卡.七月份.七月二十六号;public class test1 {public static void main(String[] args) {int[][] matrix {{1,2},{5,6},{9,10},{13,14},};print(matrix);}static void print(i…...
微服务系列(1)-who i am?
微服务系列(1)-我是谁 应用架构的演化 简单来说系统架构可以分为以下几个阶段:复杂的臃肿的单体架构-SOA架构-微服务 单体架构及其所面临的问题 在互联网发展初期,用户数量少,流量小,硬件成本高。因此…...
记录这这段时间发生的事情。
当做后端的时候总是被骂做前很丑。成为一个UI设计师与后端工程师才会更加完美。 尝试着做一个主页面。 创建了一个主页面 的表格index。 收录了希望发送到主页的,的帖子。 并且,可以填写是否可以。 一个看起来不错的主页。 标题设计的左右框。 这种框…...
发布npm包流程
发布npm包的步骤如下: 在终端中通过 npm init 命令创建一个新的npm包,按照提示填写包的信息,如包名称、版本、描述、作者、许可证等。 在包的根目录下创建一个 index.js 文件,编写你的代码。 确认你已经注册了npm账号࿰…...
面试官:Redis 为什么变慢了?怎么解决?
一、Redis为什么变慢了 二、Redis如何优化 三、Redis变慢了排查步骤 一、Redis为什么变慢了 1.Redis真的变慢了吗? 对 Redis 进行基准性能测试 例如,我的机器配置比较低,当延迟为 2ms 时,我就认为 Redis 变慢了,…...
Docker:开启应用程序开发新篇章的利器
Docker:开启应用程序开发新篇章的利器 引言:1. Docker 的基本概念2. Docker 的优势3. Docker 在应用程序开发中的实际应用如何创建docker镜像如何部署docker镜像结论: 引言: 在现代软件开发领域中,容器化技术正在迅猛…...
Python面向对象(三)(继承、封装)
面向对象的三大特性 面向对象编程,是许多编程语言都支持的一种编程思想。 简单理解是:基于模板(类)去创建实体(对象),使用对象完成功能开发。 面向对象包含3大主要特性: 封装 封…...
Redis Stream 流的深度解析与实现高级消息队列【一万字】
详细介绍了 Redis 5.0 版本新增加的数据结构Stream的使用方式以及原理,如何实现更加可靠的消息队列。 文章目录 Stream 概述2 Stream基本结构3 存储数据3.1 Entry ID3.2 数量限制 4 获取数据4.1 范围查询4.2 独立消费消息4.2.1 非阻塞使用4.2.2 阻塞的使用 4.3 消费…...
一个灵活、现代的Android应用架构
一个灵活、现代的Android应用架构 学习Android架构的原则:学习原则,不要盲目遵循规则。 本文旨在通过示例演示实际应用:通过示范Android架构来进行教学。最重要的是,这意味着展示出如何做出各种架构决策。在某些情况下࿰…...
redis高级篇 springboot+redis+bloomfilter实现过滤案例
一 bloomfilter的作用 1.1 作用 Bloomfilter:默认是有0组成bit数组和hash函数构成的数据结构,用来判断在海量数据中是否存在某个元素。 应用案例:解决缓存穿透。Bloomfilter放在redis前面,如果查询bf中没有则直接返回ÿ…...
mybatis学习笔记之在WEB中应用MyBatis
文章目录 数据库表的设计和准备数据环境搭建前端页面编写后端代码实现后端代码目录dao层servicewebpojoUtils 数据库表的设计和准备数据 环境搭建 在pom.xml中配置依赖(logback、mybatis、mysql、servlet) 注意引入tomcat 前端页面编写 <!DOCTYPE …...
宿主可以访问公网 Docker容器里无法访问 Temporary failure in name resolution
宿主可以访问公网 Docker容器里无法访问 Temporary failure in name resolution 容器参数 docker-compose.yml 的 dns我也设置,按理来说应该可以访问,然而就是不断的按在地上摩擦 web:build: .restart: alwaysports:- "6699:80"dns:- 114.11…...
CentOS7系统MBR、GRUB2、内核启动流程报错问题
目录 🥩Linux启动流程 🥩MBR修复 🍭1、模拟损坏 🍭2、重启测试 🍭3、修复MBR 🍭4、测试系统 🥩GRUB2修复 🍭1、模拟损坏 🍭2、修复GRUB2 🍭3、测试系统 &…...
剑指YOLOv5改进最新MPDIoU损失函数(23年7月首发论文):超越现有多种G/D/C/EIoU,高效准确的边界框回归的损失,高效涨点
💡本篇内容:剑指YOLOv5改进最新MPDIoU损失函数(23年7月首发论文):超越现有多种G/D/C/EIoU,高效准确的边界框回归的损失,高效涨点 💡🚀🚀🚀本博客 改进源代码改进 适用于 YOLOv5 按步骤操作运行改进后的代码即可 💡:重点:该专栏《剑指YOLOv5原创改进》只更新…...
CAN bus off ——ISO11898
什么是can bus off? CAN总线关闭(CAN bus off)是指CAN节点进入一种错误状态,无法继续正常的数据通信。当一个CAN节点的错误计数器超过了设定的阈值时,该节点将进入CAN总线关闭状态。在这种状态下,该节点将停…...
shell脚本--常见案例
1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件: 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院挂号小程序
一、开发准备 环境搭建: 安装DevEco Studio 3.0或更高版本配置HarmonyOS SDK申请开发者账号 项目创建: File > New > Create Project > Application (选择"Empty Ability") 二、核心功能实现 1. 医院科室展示 /…...
linux 错误码总结
1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...
(转)什么是DockerCompose?它有什么作用?
一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用,而无需手动一个个创建和运行容器。 Compose文件是一个文本文件,通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...
Map相关知识
数据结构 二叉树 二叉树,顾名思义,每个节点最多有两个“叉”,也就是两个子节点,分别是左子 节点和右子节点。不过,二叉树并不要求每个节点都有两个子节点,有的节点只 有左子节点,有的节点只有…...
Typeerror: cannot read properties of undefined (reading ‘XXX‘)
最近需要在离线机器上运行软件,所以得把软件用docker打包起来,大部分功能都没问题,出了一个奇怪的事情。同样的代码,在本机上用vscode可以运行起来,但是打包之后在docker里出现了问题。使用的是dialog组件,…...
力扣-35.搜索插入位置
题目描述 给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...
springboot整合VUE之在线教育管理系统简介
可以学习到的技能 学会常用技术栈的使用 独立开发项目 学会前端的开发流程 学会后端的开发流程 学会数据库的设计 学会前后端接口调用方式 学会多模块之间的关联 学会数据的处理 适用人群 在校学生,小白用户,想学习知识的 有点基础,想要通过项…...
Ubuntu系统多网卡多相机IP设置方法
目录 1、硬件情况 2、如何设置网卡和相机IP 2.1 万兆网卡连接交换机,交换机再连相机 2.1.1 网卡设置 2.1.2 相机设置 2.3 万兆网卡直连相机 1、硬件情况 2个网卡n个相机 电脑系统信息,系统版本:Ubuntu22.04.5 LTS;内核版本…...
命令行关闭Windows防火墙
命令行关闭Windows防火墙 引言一、防火墙:被低估的"智能安检员"二、优先尝试!90%问题无需关闭防火墙方案1:程序白名单(解决软件误拦截)方案2:开放特定端口(解决网游/开发端口不通)三、命令行极速关闭方案方法一:PowerShell(推荐Win10/11)方法二:CMD命令…...

