当前位置： 首页 > news >正文

leetcode42-接雨水

news 来源：原创 2025/5/14 1:31:10

leetcode 42
在这里插入图片描述

思路

本题使用 单调栈 来计算每个位置能够接住的雨水量

理解问题

题目要求计算一系列柱子之间可以接住的雨水量。输入是一个数组，每个元素代表柱子的高度。输出是一个整数，表示能够接住的水量。

找到边界条件
  • 什么情况下可以接住雨水，水量的计算依赖于柱子两边的高度，即左边界和右边界的高度
  • 确定两边高度后，能够接住的水量 由较低的边界决定
设想解决方案

考虑到要计算每一段之间的水量，可以考虑以下几种方案：

  • 暴力法：对于每一个柱子，遍历找到它左边和右边的最高柱子的高度，计算水量。这个方案复杂度较高（O(n2)），在处理大数据时会变得非常慢
  • 预处理法：可以使用两个数组存储左边和右边每个柱子的最大高度。这种方法的复杂度为 O(n) 时间和 O(n) 空间。但这并不算最优
优化思路

我们可以利用堆栈的应用，来高效的找到边界并计算水量，单调栈就可以巧妙解决此题

  • 单调栈：栈中的柱子会按高度递增。每当遇到比栈顶高的柱子时，就可以弹出栈顶元素计算水量
实现细节

从左到右遍历数组height，每当遇到更高的柱子时，就开始计算水量

  • 弹出栈顶元素，计算当前柱子与新栈顶之间的水量
  • 使用 Math.min 函数确定雨水高度，并计算当前的水量

实现

var trap = function (height) {const len = height.length;// 单调栈const stack = [0];let result = 0;for (let i = 1; i < len; i++) {while (stack.length && height[i] > height[stack[stack.length - 1]]) {const index = stack.pop();if (stack.length) {const diffHeight = Math.min(height[i], height[stack[stack.length - 1]]) - height[index];result += diffHeight * (i - stack[stack.length - 1] - 1)}}stack.push(i);}return result;
};

相关文章：

leetcode42-接雨水

leetcode 42 思路 本题使用 单调栈 来计算每个位置能够接住的雨水量 理解问题 题目要求计算一系列柱子之间可以接住的雨水量。输入是一个数组&#xff0c;每个元素代表柱子的高度。输出是一个整数&#xff0c;表示能够接住的水量。 找到边界条件 什么情况下可以接住雨水…...

编程日记 2025/5/14 1:31:10

普通IT的股票交易成长史--20250430晚

声明&#xff1a;本文章的内容只是自己学习的总结&#xff0c;不构成投资建议。文中观点基本来自yt站Andylee&#xff0c;美股Alpha姐&#xff0c;综合自己的观点得出。感谢他们的无私分享。 送给自己的话&#xff1a; 仓位就是生命&#xff0c;绝对不能满仓&#xff01;&…...

编程日记 2025/5/1 20:24:00

Elastic Security 8.18 和 9.0 中的新功能

作者&#xff1a;来自 Elastic Mark Settle, Tamarian Del Conte, James Spiteri, Tinsae Erkailo, Charles Davison, Raquel Tabuyo, Kseniia Ignatovych, Paul Ewing, Smriti 检测规则的自动迁移、用于 ES|QL 的 Lookup Join、AI 功能增强&#xff0c;以及更多功能。 Elasti…...

编程日记 2025/5/14 1:31:10

使用 Vue 开发 VS Code 插件前端页面（上）

本文的方案主要参考了这篇博客&#xff1a; Vscode 的 extension webview 开发示例&#xff1a; Vue 和 React 实现 https://juejin.cn/post/7325132202970136585样例项目地址&#xff1a; github | vscode-webview-with-vuehttps://github.com/HiMeditator/vscode-webview-w…...

编程日记 2025/5/1 20:20:54

Vue Router路由原理

Vue Router 是 Vue.js 官方的路由管理器&#xff0c;它与 Vue.js 核心深度集成&#xff0c;使得构建单页应用&#xff08;SPA&#xff09;变得非常容易。Vue Router 的主要功能包括动态路由匹配、嵌套路由、编程式导航、命名路由、路由守卫等 Vue Router 原理 单页应用&#x…...

编程日记 2025/5/1 20:17:49

Tauri v1 与 v2 配置对比

本文档对比 Tauri v1 和 v2 版本的配置结构和内容差异&#xff0c;帮助开发者了解版本变更并进行迁移。 配置结构变化 v1 配置结构 {"package": { ... },"tauri": { "allowlist": { ... },"bundle": { ... },"security":…...

编程日记 2025/5/14 1:25:06

详解 MyBatis-Plus 框架中 QueryWrapper 类

QueryWrapper 一、 QueryWrapper 的概念为什么需要 QueryWrapper&#xff1f; 二、 QueryWrapper 的基本使用1. 创建 QueryWrapper 实例2. 添加查询条件3. 执行查询 三、 QueryWrapper 的常见方法1. 基本条件方法1.1 eq - 等于1.2 ne - 不等于1.3 gt - 大于1.4 ge - 大于等于1.…...

编程日记 2025/5/14 1:30:05

小米MiMo-7B大模型：解锁推理潜力的新传奇！

在大语言模型&#xff08;LLMs&#xff09;蓬勃发展的时代&#xff0c;推理能力成为衡量模型优劣的关键指标。今天为大家解读的这篇论文&#xff0c;介绍了小米的MiMo-7B模型&#xff0c;它通过独特的预训练和后训练优化&#xff0c;展现出强大的推理实力&#xff0c;快来一探究…...

编程日记 2025/5/14 1:23:23

联邦学习的收敛性分析(全设备参与，不同本地训练轮次)

联邦学习的收敛性分析 在联邦学习中，我们的目标是分析全局模型的收敛性，考虑设备异构性（不同用户的本地训练轮次不同）和数据异质性（用户数据分布不均匀）。以下推导从全局模型更新开始，逐步引入假设并推导期望损失的递减关系，最终给出收敛性结论。 1. 全局模型更新与泰…...

编程日记 2025/5/1 19:21:25

硬件工程师面试常见问题（10）

第四十六问&#xff1a;锁存器&#xff0c;触发器&#xff0c;寄存器三者的区别 触发器&#xff1a;能够存储一位二值信号的基本单元电路统称为 "触发器"。&#xff08;单位&#xff09; 锁存器&#xff1a;一位触发器只能传送或存储一位数据&#xff0c;而在实际工…...

编程日记 2025/5/1 19:16:11

1295. 统计位数为偶数的数字

题目 解法一 遍历数组挨个判断元素位数并统计&#xff08;我的第一想法&#xff09; class Solution { public:int findNumbers(vector<int>& nums) {int result 0;for(int n: nums){if(judge(n)) result;}return result;}bool judge(int a){int sum 1;a a / 10…...

编程日记 2025/5/1 19:15:06

3.1/Q1，Charls最新文章解读

文章题目&#xff1a;Social participation patterns and associations with subsequent cognitive function in older adults with cognitive impairment: a latent class analysis DOI&#xff1a;10.3389/fmed.2025.1493359 中文标题&#xff1a;认知障碍老年人的社会参与模…...

编程日记 2025/5/14 1:30:05

楼宇智能化四章【期末复习】

四、火灾自动报警系统 结构组成：火灾探测器、区域报警器、集中报警器 形式：1. 多线制系统 2.总线制系统 3.集中智能系统 4.分布智能系统 5.网络通信系统 工作原理： 以下是关于火灾自动报警系统及相关灭火系统的详细解答： 1. 火灾自动报警系统有哪几种形式？ 区…...

编程日记 2025/5/1 19:02:28

Splunk 使用Role 实现数据隔离

很多人知道 Splunk 有很多自带的Role, 今天我就要说说定制化的Role: 1: 在创建新role 的界面: 2: 在如下的界面，可以定制allow index name： 3： 创建好新Role 后，在SAML 添加新的group 的时候，就可以看到Role 给某个group： 4： 这样一个特定组的人来申请Splunk 权限，就可…...

编程日记 2025/5/1 19:00:19

Learning vtkjs之ImplicitBoolean

隐式函数布尔操作 介绍 vtkImplicitBoolean 允许对隐式函数&#xff08;如平面、球体、圆柱体和盒子&#xff09;进行布尔组合。操作包括并集、交集和差集。可以指定多个隐式函数&#xff08;所有函数都使用相同的操作进行组合&#xff09;。 支持的操作&#xff1a;‘UNION…...

编程日记 2025/5/1 18:56:06

LabelVision - yolo可视化标注工具

LabelVision是一款可视化图像标注工具,主要用于计算机视觉研究中的各种标注任务。 支持多边形、矩形、圆形等多种标注方式&#xff0c;并且可以输出JSON、COCO等多种数据格式&#xff0c;方便与其他软件和框架进行集成和互操作。 ‌ 通过它可以很轻易的对图像进行标注,适合Y…...

编程日记 2025/5/1 18:48:45

系统分析师-第十五章

学习目标 通过参加考试&#xff0c;训练学习能力&#xff0c;而非单纯以拿证为目的。 1.在复习过程中&#xff0c;训练快速阅读能力、掌握三遍读书法、运用番茄工作法。 2.从底层逻辑角度理解知识点&#xff0c;避免死记硬背。 3.通过考试验证学习效果。 学习阶段 快速阅读 …...

编程日记 2025/5/1 18:44:33

大连理工大学选修课——机器学习笔记（3）：KNN原理及应用

KNN原理及应用 机器学习方法的分类 基于概率统计的方法 K-近邻&#xff08;KNN&#xff09;贝叶斯模型最小均值距离最大熵模型条件随机场&#xff08;CRF&#xff09;隐马尔可夫模型&#xff08;HMM&#xff09; 基于判别式的方法 决策树&#xff08;DT&#xff09;感知机…...

编程日记 2025/5/1 18:40:18

09 Python字典揭秘：数据的高效存储

文章目录 一.字典是什么1.字典的特点 二.字典的创建和使用三.字典的操作1.访问元素2.修改元素3.删除元素4.遍历字典5.成员运算 四.字典方法1.获取字典中的指定元素2.获取字典中的元素3.字典合并4.删除元素 一.字典是什么 在 Python 中&#xff0c;字典&#xff08;dict&#x…...

编程日记 2025/5/1 18:34:02

20250430在ubuntu14.04.6系统上完成编译NanoPi NEO开发板的FriendlyCore系统【严重不推荐，属于没苦硬吃】

【开始编译SDK之前需要更新源】 rootrootubuntu:~/friendlywrt-h3$ sudo apt update 【这两个目录你在ubuntu14.04.6系统上貌似git clone异常了】 Y:\friendlywrt-h3\out\wireguard Y:\friendlywrt-h3\kernel\exfat-nofuse 【需要单线程编译文件系统&#xff0c;原因不明】 Y:…...

编程日记 2025/5/1 18:24:42

第五部分：进阶项目实战

在前面的学习中&#xff0c;我们已经掌握了图像和视频的基础操作、增强滤波、特征提取以及一些基础的目标检测方法。现在&#xff0c;我们将综合运用这些知识来构建一些更复杂、更实用的应用项目。 这一部分的项目将结合前面学到的技术&#xff0c;并介绍一些新的概念和工具&a…...

编程日记 2025/5/1 18:11:11

【Linux】记录一个有用PS1

PS1 是用来定义shell提示符的环境变量 下面是一个带有颜色和丰富信息的 Linux PS1 配置示例&#xff0c;包含用户名、主机名、路径、时间、Git 分支和退出状态提示&#xff1a; # 添加到 ~/.bashrc 文件末尾 PS1\[\e[1;32m\]\u\[\e[m\] # 绿色粗体用户名 PS…...

编程日记 2025/5/14 1:12:57

【SpringBoot】基于mybatisPlus的博客管理系统（2）

目录 1.实现用户登录 Jwt令牌 1.引入依赖 2.生成令牌&#xff08;token&#xff09; Controller Service Mapper 2.实现强制登录 定义拦截器&#xff1a; 配置拦截器&#xff1a; 1.实现用户登录 在之前的项目登录中&#xff0c;我使用的是Session传递用户信息实现校验…...

编程日记 2025/5/1 18:07:01

免费在Colab运行Qwen3-0.6B——轻量高性能实战

Qwen一直在默默地接连推出新模型。 每个模型都配备了如此强大的功能和高度量化的规模，让人无法忽视。 继今年的QvQ、Qwen2.5-VL和Qwen2.5-Omni之后，Qwen团队现在发布了他们最新的模型系列——Qwen3。 这次他们不是发布一个而是发布了八个不同的模型——参数范围从6亿到235…...

编程日记 2025/5/1 18:02:52

精益数据分析（35/26）：SaaS商业模式关键指标解析

精益数据分析&#xff08;35/26&#xff09;&#xff1a;SaaS商业模式关键指标解析 在创业与数据分析的征程中&#xff0c;我们持续探索不同商业模式的运营奥秘。今天&#xff0c;我们带着共同进步的期望&#xff0c;深入研读《精益数据分析》&#xff0c;聚焦SaaS商业模式&am…...

编程日记 2025/5/4 21:02:09

【论文速读】《Scaling Scaling Laws with Board Games》

论文链接&#xff1a;https://arxiv.org/pdf/2104.03113 《Scaling Scaling Laws with Board Games》&#xff1a;探索棋盘游戏中的扩展规律 摘要 如今&#xff0c;机器学习领域中规模最大的实验所需的资源&#xff0c;超出了仅有几家机构的预算。幸运的是&#xff0c;最近的…...

编程日记 2025/5/1 17:55:34

C++ 与多技术融合的深度实践：从 AI 到硬件的全栈协同

在数字化技术高速发展的今天&#xff0c;C 凭借其卓越的性能优势和底层控制能力&#xff0c;成为连接上层应用与底层硬件的核心纽带。这种独特定位使其在与 AI 深度学习、Python 生态及硬件加速技术的融合中展现出不可替代的价值&#xff0c;构建起从算法实现到硬件优化的全栈技…...

编程日记 2025/5/1 17:52:27

AdaBoost算法的原理及Python实现

一、概述 AdaBoost&#xff08;Adaptive Boosting&#xff0c;自适应提升&#xff09;是一种迭代式的集成学习算法&#xff0c;通过不断调整样本权重&#xff0c;提升弱学习器性能&#xff0c;最终集成为一个强学习器。它继承了 Boosting 的基本思想和关键机制&#xff0c;但在…...

编程日记 2025/5/1 17:52:26

无刷马达驱动芯片算法逐步革新着风扇灯行业--其利天下

风扇灯市场热度持续攀升&#xff0c;根据行业数据&#xff0c;风扇灯市场规模从2010年的100亿元增长至2019年的200亿元&#xff0c;年均复合增长率超10%&#xff0c;预计2025年将达30%&#xff0c;借此其利天下有限公司进一步提升了无刷风扇灯驱动方案。 一、性能参数 电压&a…...

编程日记 2025/5/1 17:51:25

数据库系统综合应用与深度实践指南

前言 在当今数据驱动的时代&#xff0c;数据库技术已成为信息系统的核心支柱。从简单的数据存储到复杂的企业级应用&#xff0c;数据库系统支撑着现代社会的方方面面。本文作为一篇综合性的数据库科普文章&#xff0c;旨在为读者提供从基础到进阶的完整知识体系&#xff0c;涵…...

编程日记 2025/5/8 4:46:18

「Unity3D」TextMeshPro使用TMP_InputField实现，输入框高度自动扩展与收缩

先看实现效果&#xff1a; 要实现这个效果&#xff0c;有三个方面的问题需要解决&#xff1a; 第一&#xff0c;输入框的高度扩展&#xff0c;内部子元素会随着锚点&#xff0c;拉伸变形——要解决这个问题&#xff0c;需要将内部元素改变父类&#xff0c;然后增加父类高度&am…...

编程日记 2025/5/10 2:21:12

SAP-ABAP：在SAP系统中，COEP表（成本控制对象行项目表）详解

在SAP系统中&#xff0c;**COEP表&#xff08;成本控制对象行项目表&#xff09;**是成本控制&#xff08;CO&#xff09;模块的核心数据表之一&#xff0c;主要用于存储与成本核算相关的详细行项目数据。以下是对其作用的详细解析&#xff1a; 一、 COEP表的核心作用 存储成本…...

编程日记 2025/5/1 17:39:56

crashpad 编译

一环境配置 1.1设置系统UTF8编码 1.2vs2017语言环境设置英文包 二.获取depot_tools&#xff08;此步骤可以跳过 最新工具包已上传下载使用即可&#xff09; windows下载压缩包&#xff0c;然后放到系统PATH中 下载完以后&#xff0c;基本就是靠depot_tools这个工具集合了&am…...

编程日记 2025/5/3 6:27:02

Windows系统安装Docker（Win10系统升级，然后安装）

有时需要在自己笔记本跑下代码&#xff0c;所以安装Dockers&#xff0c;步骤如下&#xff1a; 1. 升级系统&#xff08;Windows10专业版或者Windows11&#xff09; Windows10家庭版装Docker较麻烦&#xff0c;所以我将Win10升级为Win11了&#xff08;免费&#xff09;&#x…...

编程日记 2025/5/1 17:32:37

【Fifty Project - D21】

今日完成记录 TimePlan完成情况9&#xff1a;00 - 10&#xff1a;00爬楼梯√12&#xff1a;00 - 14&#xff1a;00Leetcode√14&#xff1a;00 - 15&#xff1a;00《挪威的森林》√ Leetcode 每日一题 今天的每日一题是个easy&#xff1a;给定一个数组&#xff0c;要求统计…...

编程日记 2025/5/2 23:12:24

中央网信办部署开展“清朗·整治AI技术滥用”专项行动

为规范AI服务和应用&#xff0c;促进行业健康有序发展&#xff0c;保障公民合法权益&#xff0c;近日&#xff0c;中央网信办印发通知&#xff0c;在全国范围内部署开展为期3个月的“清朗整治AI技术滥用”专项行动。 中央网信办有关负责人表示&#xff0c;本次专项行动分两个阶…...

编程日记 2025/5/1 17:23:10

《Python实战进阶》 No46：CPython的GIL与多线程优化

Python实战进阶 No46&#xff1a;CPython的GIL与多线程优化 摘要 全局解释器锁&#xff08;GIL&#xff09;是CPython的核心机制&#xff0c;它保证了线程安全却限制了多核性能。本节通过concurrent.futures、C扩展优化和多进程架构&#xff0c;实战演示如何突破GIL限制&#…...

编程日记 2025/5/1 17:13:44

BOTA新六维力传感器PixONE：用12维度力矩与运动感测，驱动人形机器人力控未来

在机器人技术日益发展的今天&#xff0c;六维力传感器对于提升机器人感知环境、增强操作精度发挥着重要作用。瑞士BOTA Systems是一家专注于机器人传感器技术的公司&#xff0c;致力于为原始设备制造商提供高性能的传感器解决方案。 PixONE是BOTA推出的一款创新的高精度传感器&…...

编程日记 2025/5/1 17:08:31

《PyTorch documentation》（PyTorch 文档）

PyTorch documentation（PyTorch 文档） PyTorch is an optimized tensor library for deep learning using GPUs and CPUs. （PyTorch是一个优化的张量库，用于使用GPU和CPU进行深度学习。） Features described in this documentation are classified by release status: （此…...

编程日记 2025/5/1 17:08:29

数据库的死锁相关（一）

目录 前言 一、什么死锁 二、产生死锁的必要条件 三、死锁发生的具体位置和场景 1. 数据行级别死锁&#xff08;最常见&#xff09; 2. 表级别死锁 3. 索引间隙锁死锁&#xff08;InnoDB特有&#xff09; 4. 外键约束死锁 5. 元数据锁死锁 6. 内存中的锁结构死锁 7.…...

编程日记 2025/5/1 17:04:18

数据编码（Encoding）

对数据做编码可以减少存储和 I/O开销，常见的技术比如 Dictionary Encoding，Run-Length Encoding，Bitpacking，Delta Encoding，Frame-of-Reference等。 本篇文章对这些编码方案进行介绍，举例说明，最后总结各种encoding的适用场景。 一、Dictionary Encoding（字典编码）…...

编程日记 2025/5/1 17:03:14

Wartales 战争传说 [DLC 解锁] [Steam] [Windows SteamOS]

Wartales 战争传说 [DLC 解锁] [Steam] [Windows & SteamOS] DLC 版本 至最新全部 DLC 后续可能无法及时更新文章&#xff0c;具体最新版本见下载文件说明 DLC 解锁列表&#xff08;仅供参考&#xff09; 《战争传说》 - Pirates of Belerion 《战争传说》 - The Tavern …...

编程日记 2025/5/1 17:02:12

决策树在电信客户流失分析中的实战应用

在当今数据驱动的时代&#xff0c;数据分析和机器学习技术在各行业的应用愈发广泛。电信行业面临着激烈的竞争&#xff0c;客户流失问题成为影响企业发展的关键因素之一。如何准确预测客户是否会流失&#xff0c;并采取相应措施挽留客户&#xff0c;是电信企业关注的重点。决策…...

编程日记 2025/5/1 17:01:10

滚珠丝杆怎么选型？

滚珠丝杆的选型需要考虑多个因素&#xff0c;包括应用需求、性能参数、环境因素等&#xff0c;以确保选型的准确性和合理性。 1、负载&#xff1a;确定设备运行时滚珠丝杆需要承受的静载荷和动载荷&#xff0c;包括轴向载荷和径向载荷&#xff0c;根据实际工作情况计算出最大负…...

编程日记 2025/5/1 17:01:09

HTN77A0原理图提供聚能芯半导体禾润一级代理技术支持免费送样

在电源管理需求日益严苛的当下&#xff0c;禾润 HTN77A0 以卓越性能脱颖而出。它不仅适配多种应用场景&#xff0c;还兼具高效节能与稳定输出&#xff0c;为设备供能带来革新体验。 禾润 HTN77A0 同步降压变换器&#xff0c;凭借5V~130V 超宽输入电压范围&#xff0c;打破传统供…...

编程日记 2025/5/9 16:21:30

linux中sigint和sigterm的区别

SIGINT 和 SIGTERM 是在 Unix 及类 Unix 系统&#xff08;包括 Linux&#xff09;中用于进程间通信的信号&#xff0c;它们都可以用于请求进程终止&#xff0c;区别如下&#xff1a; 1、信号编号与定义 在信号机制里&#xff0c;每个信号都有对应的编号&#xff0c;这便于系统…...

编程日记 2025/5/1 16:50:42

errorno 和WSAGetlasterror的区别

errno 和 WSAGetLastError 是用于获取错误代码的机制&#xff0c;但它们应用于不同的编程场景&#xff0c;下面为你详细介绍二者的区别&#xff1a; 应用场景 errno&#xff1a;它是 C 和 C 等编程语言里用于表示系统调用和库函数错误的全局变量。在 Unix、Linux 等类 Unix 系…...

编程日记 2025/5/1 16:47:34

《操作系统真象还原》第十一章——用户进程

文章目录 前言为什么要有TSSTSS简介TSS描述符和TSS结构现代操作系统采用的任务切换方式 定义并初始化TSS修改global.h编写tss.c测试 实现用户进程实现用户进程的原理维护虚拟地址空间&#xff0c;修改thread.h为进程创建页表和3特权级栈&#xff0c;修改memory.c进入特权级3用户…...

编程日记 2025/5/1 16:42:21

第 11 届蓝桥杯 C++ 青少组中 / 高级组省赛 2020 年真题答和案解析

一、选择题 第 1 题 单选题 题目：表达式 ‘6’ - ‘1’ 的值是 ( ) A. 整数 5 B. 字符 5 C. 表达式不合法 D. 字符 6 答案：A 解析：在 C++ 中，字符常量以 ASCII 码形式存储。6 的 ASCII 码为 54，1 的 ASCII 码为 49，二者相减结果为 5，是整数类型，因此选 A。 第 2 题 …...

编程日记 2025/5/1 16:41:14

ES搜索知识

GET /categories/1/10?name手机 // 按名称过滤 GET /categories/1/10?type电子产品 // 按类型过滤 GET /categories/1/10?name手机&type电子产品 // 组合过滤 查询参数 ApiOperation(value "获取商品分类分页列表")GetMapping("{page}/{limit}")…...

编程日记 2025/5/1 16:41:13