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

【力扣刷题练习】42. 接雨水

题目描述:

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。

题目解答:

class Solution {public int trap(int[] height) {int n = height.length;int ans = 0;if (n < 3)return ans;int left = 0, right = n - 1;int maxl = 0, maxr = 0;while (left < right) {maxl = Math.max(maxl, height[left]);maxr = Math.max(maxr, height[right]);ans += maxl < maxr ? maxl - height[left++] : maxr - height[right--];}return ans;}
}

题目思路:

双指针法在这段代码中的思想是通过两个指针分别从数组的两端向中间移动,同时维护左侧和右侧的最大高度。这种方法可以有效地减少计算量,因为在移动过程中,我们只关心较小的一侧的最大高度来计算雨水量。

  1. 初始化:

    • 初始化两个指针 leftright 分别指向数组的开头和末尾。
    • 初始化两个变量 maxlmaxr 分别表示左侧和右侧的最大高度,初始值为 0。
    int left = 0, right = n - 1;
    int maxl = 0, maxr = 0;
    
  2. 移动指针:

    • 在循环中,通过比较 maxlmaxr 的大小,选择较小的一侧。
    • 如果 maxl 小于 maxr,说明左侧最高柱子决定了当前位置的雨水高度,因此计算当前位置的雨水量,并将结果累加到 ans 中。
    • 根据选择的最小高度,移动对应的指针,向中间靠拢。
    while (left < right) {maxl = Math.max(maxl, height[left]);maxr = Math.max(maxr, height[right]);ans += maxl < maxr ? maxl - height[left++] : maxr - height[right--];
    }
    
  3. 核心思想:

    • 在每一步中,都选择较小的一侧,这样可以确保当前位置的雨水量是由较小的一侧的最大高度决定的。
    • 移动指针时,总是移动较小一侧的指针,这样可以确保在移动的过程中,雨水的计算仍然是以较小的一侧为基准。

通过这种双指针的思想,代码在一次遍历中完成了整个计算过程,而不需要额外的空间,从而实现了较好的时间复杂度。这种方法的关键在于巧妙地使用两个指针来同时遍历数组,减少了不必要的计算,提高了算法的效率。

其中使用了条件运算符(三元运算符),其形式为:

//result = condition ? expression_if_true : expression_if_false;
ans += maxl < maxr ? maxl - height[left++] : maxr - height[right--];

我们可以拆解它的含义:

  1. maxl < maxr 表示当前左侧的最大高度小于右侧的最大高度。
  2. 如果条件成立(true),则选择 maxl - height[left++],表示当前位置的雨水量是由左侧的最大高度决定的,然后将 left 指针向右移动。
  3. 如果条件不成立(false),则选择 maxr - height[right--],表示当前位置的雨水量是由右侧的最大高度决定的,然后将 right 指针向左移动。

整体来看,这行代码实现了双指针移动的逻辑,根据左右两侧的最大高度之间的关系来决定当前位置的雨水量。选择较小的一侧作为决定因素,计算雨水量,然后移动相应的指针,使问题规模减小,最终完成整个遍历过程。

这种表达方式是为了避免使用额外的 if-else 语句,通过条件运算符直接在一行中完成逻辑。这样的写法简洁而清晰,同时保持了代码的可读性。

相关文章:

【力扣刷题练习】42. 接雨水

题目描述&#xff1a; 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图&#xff0c;计算按此排列的柱子&#xff0c;下雨之后能接多少雨水。 题目解答&#xff1a; class Solution {public int trap(int[] height) {int n height.length;int ans 0;if (n < 3)return…...

鸿蒙实战开发:数据交互【RPC连接】

概述 本示例展示了同一设备中前后台的数据交互&#xff0c;用户前台选择相应的商品与数目&#xff0c;后台计算出结果&#xff0c;回传给前台展示。 样例展示 基础信息 RPC连接 介绍 本示例使用[ohos.rpc]相关接口&#xff0c;实现了一个前台选择商品和数目&#xff0c;后台…...

QLC SSD:LDPC纠错算法的优化方案

随着NAND TLC和QLC出现,LDPC也在不断的优化研究,提升纠错能力。小编看到有一篇来自Microchip发布的比较详细的LDPC研究数据,根据自己的理解分析解读给大家,如有错误,请留言指正! 文档中测试LDPC(Low-Density Parity-Check)码是为了评估其在不同配置下对数据错误的有效…...

【Flutter 面试题】main()和runApp()函数在Flutter的作用分别是什么?有什么关系吗?

【Flutter 面试题】main()和runApp()函数在Flutter的作用分别是什么&#xff1f;有什么关系吗&#xff1f; 文章目录 写在前面解答补充说明 写在前面 关于我 &#xff0c;小雨青年 &#x1f449; CSDN博客专家&#xff0c;GitChat专栏作者&#xff0c;阿里云社区专家博主&…...

ChatGPT高效提问——说明提示技巧

ChatGPT高效提问——说明提示技巧 现在&#xff0c;让我们开始体验“说明提示技巧”&#xff08;IPT, Instructions Prompt Technique&#xff09;和如何用它生成来自ChatGPT的高质量的文本。说明提示技巧是一个通过向ChatGPT提供需要依据的具体的模型的说明来指导ChatGPT输出…...

从零学算法41

41.给你一个未排序的整数数组 nums &#xff0c;请你找出其中没有出现的最小的正整数。 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。 示例 1&#xff1a; 输入&#xff1a;nums [1,2,0] 输出&#xff1a;3 示例 2&#xff1a; 输入&#xff1a;nums […...

FPGA高端项目:FPGA基于GS2971的SDI视频接收+OSD动态字符叠加,提供1套工程源码和技术支持

目录 1、前言免责声明 2、相关方案推荐本博已有的 SDI 编解码方案本方案的SDI接收转HDMI输出应用本方案的SDI接收图像缩放应用本方案的SDI接收纯verilog图像缩放纯verilog多路视频拼接应用本方案的SDI接收HLS图像缩放HLS多路视频拼接应用本方案的SDI接收HLS多路视频融合叠加应用…...

UML-类图详解

UML中基本概念说明 UML类图中关系连接线说明 ​ UML类图说明 号表示public、-表示表示private、#表示protected ​ UML类关系详解 泛化&#xff08;Generalization&#xff09;关系 简单的讲就是类之间的继承关系。在UML中&#xff0c;泛化关系用空心三角形实线来表示&…...

Python 快速获取PDF文件的页数

有时在处理或打印一个PDF文档之前&#xff0c;你可能需要先知道该文档包含多少页。虽然我们可以使用Adobe Acrobat这样的工具来查看页数&#xff0c;但对于程序员来说&#xff0c;编写脚本来完成这项工作会更加高效。本文就介绍一个使用Python快速获取PDF文件页数的办法。 安装…...

uniapp开发小程序使用x-www-form-urlencoded; charset=UTF-8 编码格式请求案例

使用x-www-form-urlencoded&#xff0c;header要放在前面&#xff0c;第一行位置。 uni.request({ header: { content-type: application/x-www-form-urlencoded; charsetUTF-8},url: ,method:POST, //请求方式POST\GETdata:that.loginData,success: funct…...

酷开科技服务升级,酷开系统给消费者更好的使用体验!

看电视的时候你是不是也会有选择困难症&#xff1f;不知道要看哪个&#xff1f;不知道如何操作&#xff1f;体验不够顺畅&#xff1f;现在&#xff0c;有了酷开系统9.2&#xff0c;这些通通不再是问题&#xff01;酷开科技&#xff0c;一直致力于服务升级&#xff0c;给消费者更…...

【leetcode热题】单词拆分

难度&#xff1a; 中等通过率&#xff1a; 33.7%题目链接&#xff1a;. - 力扣&#xff08;LeetCode&#xff09; 题目描述 给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict&#xff0c;判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。 说明&#…...

【论文阅读】MC:用于语义图像分割的深度卷积网络弱监督和半监督学习

【论文阅读】MC&#xff1a;用于语义图像分割的深度卷积网络弱监督和半监督学习 文章目录 【论文阅读】MC&#xff1a;用于语义图像分割的深度卷积网络弱监督和半监督学习一、介绍二、联系工作三、方法四、实验结果 Weakly- and Semi-Supervised Learning of a Deep Convolutio…...

读书·基于RISC-V和FPGA的嵌入式系统设计·第3章

72.8051单片机的弊端和指令集架构CISC的缺点 76.RV指令集的特征&#xff08;⭐&#xff09; 特权架构和特权指令集是相关但不完全相同的概念。 特权架构&#xff08;Privileged Architecture&#xff09;指的是计算机体系结构中用于实现特权级操作的硬件和软件机制。特权架构定…...

本地项目推送到腾讯云轻量应用服务器教程(并实现本地推送远程自动更新)

将本地项目上传到腾讯云轻量应用服务器并实现后续的推送更新&#xff0c;具体步骤如下&#xff1a; 在本地项目目录下初始化 Git 仓库&#xff1a; cd 项目目录 git init将项目文件添加到 Git 仓库并提交&#xff1a; git add . git commit -m "Initial commit"在…...

MacOS安装反编译工具JD-GUI 版本需要1.8+

Java Decompiler http://java-decompiler.github.io/ 将下载下来的 jd-gui-osx-1.6.6.tar 解压&#xff0c;然后将 JD-GUI.app 文件拷贝到 Applications 应用程序目录里面 1.显示包内容 2.找到Contents/MacOS/universalJavaApplicationStub.sh 3.修改sh文件 内容修改为下面…...

计算机大数据毕业设计-基于Flask的旅游推荐可视化系统的设计与实现

基于Flask的旅游推荐可视化系统的设计与实现 编程语言&#xff1a;Python3.10 涉及技术&#xff1a;FlaskMySQL8.0Echarts 开发工具&#xff1a;PyCharm 摘要&#xff1a;以Pycharm为旅游推荐系统开发工具&#xff0c;采用B/S结构&#xff0c;使用Python语言开发旅游景点推…...

java实现pdf转word

java实现pdf转word 前言pom文件启动入口过滤器对象ConvertPdfToWordWithFlowableStructure转换实现类 前言 1.java实现pdf转word。 2.纯免费开源。 3.pdf解析完会生成word文件和图片文件夹。 4.无页码限制&#xff0c;文本类型生成到word中&#xff0c;图片生成到图片文件夹中…...

【操作系统概念】 第4章:线程

文章目录 0.前言4.1 概述4.1.1 多线程编程的优点 4.2 多线程模型4.2.1 多对一模型4.2.2 一对一模型4.2.3 多对多模型 4.3 线程库4.4 多线程问题4.4.1 系统调用fork()和exec()4.4.2 取消4.4.3 信号处理4.4.4 线程池4.4.5 线程特定数据 0.前言 第3章讨论的进程模型假设每个进程是…...

STM32/GD32——I2C通信协议

芯片选型 Ciga Device — GD32F470系列 通讯规则 I2C协议&#xff08;或称IIC&#xff09;是由飞利浦&#xff08;现在的恩智浦半导体&#xff09;公司开发的一种通用的总线协议。它使用两根线&#xff08;时钟线和数据线&#xff09;来传输数据&#xff0c;支持多个设备共享…...

[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?

论文网址&#xff1a;pdf 英文是纯手打的&#xff01;论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误&#xff0c;若有发现欢迎评论指正&#xff01;文章偏向于笔记&#xff0c;谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...

【Go】3、Go语言进阶与依赖管理

前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课&#xff0c;做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程&#xff0c;它的核心机制是 Goroutine 协程、Channel 通道&#xff0c;并基于CSP&#xff08;Communicating Sequential Processes&#xff0…...

前端开发面试题总结-JavaScript篇(一)

文章目录 JavaScript高频问答一、作用域与闭包1.什么是闭包&#xff08;Closure&#xff09;&#xff1f;闭包有什么应用场景和潜在问题&#xff1f;2.解释 JavaScript 的作用域链&#xff08;Scope Chain&#xff09; 二、原型与继承3.原型链是什么&#xff1f;如何实现继承&a…...

CMake控制VS2022项目文件分组

我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...

【生成模型】视频生成论文调研

工作清单 上游应用方向&#xff1a;控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...

算法:模拟

1.替换所有的问号 1576. 替换所有的问号 - 力扣&#xff08;LeetCode&#xff09; ​遍历字符串​&#xff1a;通过外层循环逐一检查每个字符。​遇到 ? 时处理​&#xff1a; 内层循环遍历小写字母&#xff08;a 到 z&#xff09;。对每个字母检查是否满足&#xff1a; ​与…...

Linux系统部署KES

1、安装准备 1.版本说明V008R006C009B0014 V008&#xff1a;是version产品的大版本。 R006&#xff1a;是release产品特性版本。 C009&#xff1a;是通用版 B0014&#xff1a;是build开发过程中的构建版本2.硬件要求 #安全版和企业版 内存&#xff1a;1GB 以上 硬盘&#xf…...

零知开源——STM32F103RBT6驱动 ICM20948 九轴传感器及 vofa + 上位机可视化教程

STM32F1 本教程使用零知标准板&#xff08;STM32F103RBT6&#xff09;通过I2C驱动ICM20948九轴传感器&#xff0c;实现姿态解算&#xff0c;并通过串口将数据实时发送至VOFA上位机进行3D可视化。代码基于开源库修改优化&#xff0c;适合嵌入式及物联网开发者。在基础驱动上新增…...

ZYNQ学习记录FPGA(一)ZYNQ简介

一、知识准备 1.一些术语,缩写和概念&#xff1a; 1&#xff09;ZYNQ全称&#xff1a;ZYNQ7000 All Pgrammable SoC 2&#xff09;SoC:system on chips(片上系统)&#xff0c;对比集成电路的SoB&#xff08;system on board&#xff09; 3&#xff09;ARM&#xff1a;处理器…...

【FTP】ftp文件传输会丢包吗?批量几百个文件传输,有一些文件没有传输完整,如何解决?

FTP&#xff08;File Transfer Protocol&#xff09;本身是一个基于 TCP 的协议&#xff0c;理论上不会丢包。但 FTP 文件传输过程中仍可能出现文件不完整、丢失或损坏的情况&#xff0c;主要原因包括&#xff1a; ✅ 一、FTP传输可能“丢包”或文件不完整的原因 原因描述网络…...