力扣热门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总线关闭状态。在这种状态下,该节点将停…...
PHP和Node.js哪个更爽?
先说结论,rust完胜。 php:laravel,swoole,webman,最开始在苏宁的时候写了几年php,当时觉得php真的是世界上最好的语言,因为当初活在舒适圈里,不愿意跳出来,就好比当初活在…...
Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例
使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件,常用于在两个集合之间进行数据转移,如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model:绑定右侧列表的值&…...
2024年赣州旅游投资集团社会招聘笔试真
2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...
django filter 统计数量 按属性去重
在Django中,如果你想要根据某个属性对查询集进行去重并统计数量,你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求: 方法1:使用annotate()和Count 假设你有一个模型Item,并且你想…...
python如何将word的doc另存为docx
将 DOCX 文件另存为 DOCX 格式(Python 实现) 在 Python 中,你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是,.doc 是旧的 Word 格式,而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...
在Ubuntu24上采用Wine打开SourceInsight
1. 安装wine sudo apt install wine 2. 安装32位库支持,SourceInsight是32位程序 sudo dpkg --add-architecture i386 sudo apt update sudo apt install wine32:i386 3. 验证安装 wine --version 4. 安装必要的字体和库(解决显示问题) sudo apt install fonts-wqy…...
并发编程 - go版
1.并发编程基础概念 进程和线程 A. 进程是程序在操作系统中的一次执行过程,系统进行资源分配和调度的一个独立单位。B. 线程是进程的一个执行实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位。C.一个进程可以创建和撤销多个线程;同一个进程中…...
根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的----NTFS源代码分析--重要
根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的 第一部分: 0: kd> g Breakpoint 9 hit Ntfs!ReadIndexBuffer: f7173886 55 push ebp 0: kd> kc # 00 Ntfs!ReadIndexBuffer 01 Ntfs!FindFirstIndexEntry 02 Ntfs!NtfsUpda…...
Ubuntu Cursor升级成v1.0
0. 当前版本低 使用当前 Cursor v0.50时 GitHub Copilot Chat 打不开,快捷键也不好用,当看到 Cursor 升级后,还是蛮高兴的 1. 下载 Cursor 下载地址:https://www.cursor.com/cn/downloads 点击下载 Linux (x64) ,…...
GraphQL 实战篇:Apollo Client 配置与缓存
GraphQL 实战篇:Apollo Client 配置与缓存 上一篇:GraphQL 入门篇:基础查询语法 依旧和上一篇的笔记一样,主实操,没啥过多的细节讲解,代码具体在: https://github.com/GoldenaArcher/graphql…...

