力扣热门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总线关闭状态。在这种状态下,该节点将停…...
网络六边形受到攻击
大家读完觉得有帮助记得关注和点赞!!! 抽象 现代智能交通系统 (ITS) 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 (…...
ES6从入门到精通:前言
ES6简介 ES6(ECMAScript 2015)是JavaScript语言的重大更新,引入了许多新特性,包括语法糖、新数据类型、模块化支持等,显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var…...
【解密LSTM、GRU如何解决传统RNN梯度消失问题】
解密LSTM与GRU:如何让RNN变得更聪明? 在深度学习的世界里,循环神经网络(RNN)以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而,传统RNN存在的一个严重问题——梯度消失&#…...
【大模型RAG】Docker 一键部署 Milvus 完整攻略
本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装;只需暴露 19530(gRPC)与 9091(HTTP/WebUI)两个端口,即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...
Python爬虫(二):爬虫完整流程
爬虫完整流程详解(7大核心步骤实战技巧) 一、爬虫完整工作流程 以下是爬虫开发的完整流程,我将结合具体技术点和实战经验展开说明: 1. 目标分析与前期准备 网站技术分析: 使用浏览器开发者工具(F12&…...
linux 下常用变更-8
1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行,YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID: YW3…...
分布式增量爬虫实现方案
之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面,避免重复抓取,以节省资源和时间。 在分布式环境下,增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路:将增量判…...
tomcat指定使用的jdk版本
说明 有时候需要对tomcat配置指定的jdk版本号,此时,我们可以通过以下方式进行配置 设置方式 找到tomcat的bin目录中的setclasspath.bat。如果是linux系统则是setclasspath.sh set JAVA_HOMEC:\Program Files\Java\jdk8 set JRE_HOMEC:\Program Files…...
Axure 下拉框联动
实现选省、选完省之后选对应省份下的市区...
【免费数据】2005-2019年我国272个地级市的旅游竞争力多指标数据(33个指标)
旅游业是一个城市的重要产业构成。旅游竞争力是一个城市竞争力的重要构成部分。一个城市的旅游竞争力反映了其在旅游市场竞争中的比较优势。 今日我们分享的是2005-2019年我国272个地级市的旅游竞争力多指标数据!该数据集源自2025年4月发表于《地理学报》的论文成果…...

