当前位置: 首页 > 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;支持多个设备共享…...

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式

一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明&#xff1a;假设每台服务器已…...

浅谈 React Hooks

React Hooks 是 React 16.8 引入的一组 API&#xff0c;用于在函数组件中使用 state 和其他 React 特性&#xff08;例如生命周期方法、context 等&#xff09;。Hooks 通过简洁的函数接口&#xff0c;解决了状态与 UI 的高度解耦&#xff0c;通过函数式编程范式实现更灵活 Rea…...

日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻

在如今就业市场竞争日益激烈的背景下&#xff0c;越来越多的求职者将目光投向了日本及中日双语岗位。但是&#xff0c;一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧&#xff1f;面对生疏的日语交流环境&#xff0c;即便提前恶补了…...

python打卡day49

知识点回顾&#xff1a; 通道注意力模块复习空间注意力模块CBAM的定义 作业&#xff1a;尝试对今天的模型检查参数数目&#xff0c;并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...

LeetCode - 394. 字符串解码

题目 394. 字符串解码 - 力扣&#xff08;LeetCode&#xff09; 思路 使用两个栈&#xff1a;一个存储重复次数&#xff0c;一个存储字符串 遍历输入字符串&#xff1a; 数字处理&#xff1a;遇到数字时&#xff0c;累积计算重复次数左括号处理&#xff1a;保存当前状态&a…...

相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)

【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...

Spring AI 入门:Java 开发者的生成式 AI 实践之路

一、Spring AI 简介 在人工智能技术快速迭代的今天&#xff0c;Spring AI 作为 Spring 生态系统的新生力量&#xff0c;正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务&#xff08;如 OpenAI、Anthropic&#xff09;的无缝对接&…...

Caliper 配置文件解析:config.yaml

Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...

网站指纹识别

网站指纹识别 网站的最基本组成&#xff1a;服务器&#xff08;操作系统&#xff09;、中间件&#xff08;web容器&#xff09;、脚本语言、数据厍 为什么要了解这些&#xff1f;举个例子&#xff1a;发现了一个文件读取漏洞&#xff0c;我们需要读/etc/passwd&#xff0c;如…...

C++:多态机制详解

目录 一. 多态的概念 1.静态多态&#xff08;编译时多态&#xff09; 二.动态多态的定义及实现 1.多态的构成条件 2.虚函数 3.虚函数的重写/覆盖 4.虚函数重写的一些其他问题 1&#xff09;.协变 2&#xff09;.析构函数的重写 5.override 和 final关键字 1&#…...