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

接雨水

接雨水

  • 1、 题目描述
  • 2、解题思路

1、 题目描述

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

2、解题思路

本题使用了双指针,根据下图可以得出,下标 i 处能接的雨水量由左边最大值 leftMax 和右边最大值 rightMax 中的最小值决定,因此设置左指针left和右指针right,左指针只会向右移动,右指针只会向左移动,遍历的过程中持续更新 leftMax 和 rightMax 。

  • 若 leftMax < rightMax,下标 left 处能接的雨水量等于 leftMax−height[left],将下标 left 处能接的雨水量加到能接的雨水总量,然后将 left 加 1(即向右移动一位)
  • 若 leftMax ≥ rightMax,下标 right 处能接的雨水量等于 rightMax−height[right],将下标 right 处能接的雨水量加到能接的雨水总量,然后将 right 减 1(即向左移动一位)

在这里插入图片描述

class Solution {public int trap(int[] height) {// 定义左右指针int left=0,right=height.length-1;// 定义左边最大值和右边最大值int leftMax=0,rightMax=0;// 定义最终结果int ans = 0;// 两个指针相遇为循环结束条件while(left<right){// 判断当前高度是否比最大高度大,若是,更新最大高度if(height[left]>leftMax)leftMax = height[left];if(height[right]>rightMax)rightMax = height[right];// 下标i处能接到的雨水量由leftMax和rightMax的最小值决定if(leftMax<rightMax){ans += leftMax-height[left];left++;}else{ans += rightMax-height[right];right--;}}return ans;}
}
  • 时间复杂度:O(n),其中 n 是数组 height 的长度。两个指针的移动总次数不超过 n。
  • 空间复杂度:O(1)。只需要使用常数的额外空间。

相关文章:

接雨水

接雨水 1、 题目描述2、解题思路 1、 题目描述 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图&#xff0c;计算按此排列的柱子&#xff0c;下雨之后能接多少雨水。 2、解题思路 本题使用了双指针&#xff0c;根据下图可以得出&#xff0c;下标 i 处能接的雨水量由左边…...

Python蓝桥杯刷题1

1.确定字符串是否包含唯一字符 题解&#xff1a;调用count函数计算每一个字符出现的次数&#xff0c;如果不等于1就输出no&#xff0c;并且结束循环&#xff0c;如果等于1就一直循环直到计算到最后一个字符&#xff0c;若最后一个字符也满足条件&#xff0c;则输出yes import…...

实习冲刺第二十七天

3.无重复字符的最长字串 给定一个字符串 s &#xff0c;请你找出其中不含有重复字符的 最长 子串 的长度。 示例 1: 输入: s "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"&#xff0c;所以其长度为 3。示例 2: 输入: s "bbbb…...

el-table-column自动生成序号在序号前插入图标

实现效果&#xff1a; 代码如下&#xff1a; 在el-table里加入这个就可以了&#xff0c;需要拿到值可以用scope.$index ​​​​​​​<el-table-column type"index" label"序号" show-overflow-tooltip"true" min-width"40">…...

前端工程化-node/npm/babel/polyfill/webpack 一文速通

文章主要介绍了前端工程化的相关内容&#xff0c;包括 Node 环境、npm 包管理器及其命令、配置和镜像&#xff0c;package.json 文件&#xff0c;babel 和 polyfill 用于解决 JavaScript 兼容性问题&#xff0c;以及 webpack 这一前端构建工具的作用、核心概念、构建流程、安装…...

Spring Security PasswordEncoder接口(密码编码)

密码编码&#xff08;通常称为哈希&#xff09;是一种安全措施&#xff0c;它将明文密码转换为独特的字符字符串。 主要目的是确保即使数据存储遭到破坏&#xff0c;存储的密码也不会轻易被破解。 与加密不同&#xff0c;哈希是一个单向过程——这意味着无法从哈希值中恢复原…...

C# 数据结构之【树】C#树

以二叉树为例进行演示。二叉树每个节点最多有两个子节点。 1. 新建二叉树节点模型 using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks;namespace DataStructure {class TreeNode{public int Data { get;…...

树莓派2装FreeBSD14.1 Raspberry Pi2 install FreeBSD14.1 00000121:error:0A000086:SSL

树莓派2代的Model B采用Broadcom BCM2836 900MHz的四核SoC&#xff0c;1GB内存&#xff0c;是新一代开拓者&#xff0c;兼容1代B。相比之下&#xff0c;树莓派2的性能比1代提升6倍&#xff0c;内存翻了一番。Raspberry Pi 2不仅能跑全系列ARM GNU/Linux发行版&#xff0c;而且支…...

探索C/C++的奥秘之stack和queue

1. stack的介绍和使用 1.1 stack的介绍 1. stack是一种容器适配器&#xff0c;专门用在具有后进先出操作的上下文环境中&#xff0c;其删除只能从容器的一端进行元素的插入与提取操作。具体什么是适配器呢&#xff1f;其实就是由现有的东西进行转换&#xff0c;转化出我要的东…...

[开源]1.2K star!中后台方向的低代码可视化平台,超赞!

大家好&#xff0c;我是JavaCodexPro&#xff01; “时间就是金钱&#xff0c;效率就是生命”&#xff0c;快速搭建高质量中后台的低代码可视化搭建平台尤为重要&#xff01; 今天JavaCodexPro给大家分享一款超赞的低代码可视化搭建平台 - Marsview &#xff0c;旨在简化开发…...

算法编程题-排序

算法编程题-排序 比较型排序算法冒泡排序选择排序插入排序希尔排序堆排序快速排序归并排序 非比较型排序算法计数排序基数排序 本文将对七中经典比较型排序算法进行介绍&#xff0c;并且给出golang语言的实现&#xff0c;还包括基数排序、计数排序等非比较型的算法的介绍和实现…...

【AIGC】如何准确引导ChatGPT,实现精细化GPTs指令生成

博客主页&#xff1a; [小ᶻZ࿆] 本文专栏: AIGC | 提示词Prompt应用实例 文章目录 &#x1f4af;前言&#x1f4af;准确引导ChatGPT创建爆款小红书文案GPTs指令案例&#x1f4af; 高效开发GPTs应用的核心原则明确应用场景和目标受众构建多样化风格模板提问与引导技巧持续优…...

【Axure高保真原型】或和且条件

今天和大家分享或和且条件案例的原型模板&#xff0c;效果包括&#xff1a; 可以选择指标、等式和填写对应值构成条件等式&#xff1b; 点击添加条件按钮&#xff0c;可以增加一行新的条件&#xff1b; 点击所在行的号按钮&#xff0c;可以在该行下方添加一行新的条件&#x…...

KubeVirt下gpu operator实践(GPU直通)

KubeVirt下gpu operator实践(GPU直通) 参考《在 KubeVirt 中使用 GPU Operator》&#xff0c;记录gpu operator在KubeVirt下实践的过程&#xff0c;包括虚拟机配置GPU直通&#xff0c;容器挂载GPU设备等。 KubeVirt 提供了一种将主机设备分配给虚拟机的机制。该机制具有通用性…...

Vue通过file控件上传文件到Node服务器

功能&#xff1a; 1.多文件同时上传、2.拖动上传、3.实时上传进度条、4.中断上传和删除文件、5.原生file控件的美化 搁置的功能: 上传文件夹、大文件切片上传、以及其他限制条件未处理 Node服务器的前置准备: 新建文件夹: file_upload_serve初始化npm: npm …...

如何在 SQL Server 中新增账户并指定数据库权限

在日常的数据库维护与开发中,管理用户的权限是必不可少的一环。本文将指导你如何在 SQL Server 中为新用户创建账户,并为其指定相应的数据库权限,使其只能查看有权访问的数据。我们将以步骤和代码示例的方式展示整个流程。用户权限分配包括:读取权限、写入权限、执行权限。…...

c#编码技巧(十九):各种集合特点汇总

.NET 常用集合对比&#xff1a; .NET 常见的线程安全集合 .NET 只读集合...

汽车软件DevOps解决方案

汽车软件DevOps解决方案是专为现代汽车行业设计的一套集成化需求、开发、测试、部署、OTA与监控&#xff0c;旨在加速软件开发流程&#xff0c;提高软件质量和安全性&#xff0c;同时确保整个生命周期的高效性和灵活性。以下是经纬恒润汽车软件DevOps解决方案的关键组成部分和优…...

同步的意义以及机制

一、同步的意义 同步&#xff08;Synchronization&#xff09;的意义在于确保在多线程环境中&#xff0c;多个线程对共享资源的访问是安全的&#xff0c;避免竞争条件&#xff08;race conditions&#xff09;和数据不一致的情况。 具体来说&#xff0c;同步的核心目标是&…...

leetcode 面试150之 156.LUR 缓存

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。 实现 LRUCache 类&#xff1a; LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存int get(int key) 如果关键字 key 存在于缓存中&#xff0c;则返回关键字的值&#xff0c;否则返回 -…...

浅谈 React Hooks

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

生成xcframework

打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式&#xff0c;可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...

【Python】 -- 趣味代码 - 小恐龙游戏

文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...

stm32G473的flash模式是单bank还是双bank?

今天突然有人stm32G473的flash模式是单bank还是双bank&#xff1f;由于时间太久&#xff0c;我真忘记了。搜搜发现&#xff0c;还真有人和我一样。见下面的链接&#xff1a;https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...

突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合

强化学习&#xff08;Reinforcement Learning, RL&#xff09;是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程&#xff0c;然后使用强化学习的Actor-Critic机制&#xff08;中文译作“知行互动”机制&#xff09;&#xff0c;逐步迭代求解…...

深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法

深入浅出&#xff1a;JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中&#xff0c;随机数的生成看似简单&#xff0c;却隐藏着许多玄机。无论是生成密码、加密密钥&#xff0c;还是创建安全令牌&#xff0c;随机数的质量直接关系到系统的安全性。Jav…...

为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?

在建筑行业&#xff0c;项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升&#xff0c;传统的管理模式已经难以满足现代工程的需求。过去&#xff0c;许多企业依赖手工记录、口头沟通和分散的信息管理&#xff0c;导致效率低下、成本失控、风险频发。例如&#…...

定时器任务——若依源码分析

分析util包下面的工具类schedule utils&#xff1a; ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类&#xff0c;封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz&#xff0c;先构建任务的 JobD…...

【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】

1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件&#xff08;System Property Definition File&#xff09;&#xff0c;用于声明和管理 Bluetooth 模块相…...

【HTTP三个基础问题】

面试官您好&#xff01;HTTP是超文本传输协议&#xff0c;是互联网上客户端和服务器之间传输超文本数据&#xff08;比如文字、图片、音频、视频等&#xff09;的核心协议&#xff0c;当前互联网应用最广泛的版本是HTTP1.1&#xff0c;它基于经典的C/S模型&#xff0c;也就是客…...