当前位置: 首页 > 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;否则返回 -…...

零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?

一、核心优势&#xff1a;专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发&#xff0c;是一款收费低廉但功能全面的Windows NAS工具&#xff0c;主打“无学习成本部署” 。与其他NAS软件相比&#xff0c;其优势在于&#xff1a; 无需硬件改造&#xff1a;将任意W…...

DockerHub与私有镜像仓库在容器化中的应用与管理

哈喽&#xff0c;大家好&#xff0c;我是左手python&#xff01; Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库&#xff0c;用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...

Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)

文章目录 1.什么是Redis&#xff1f;2.为什么要使用redis作为mysql的缓存&#xff1f;3.什么是缓存雪崩、缓存穿透、缓存击穿&#xff1f;3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...

Linux简单的操作

ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院挂号小程序

一、开发准备 ​​环境搭建​​&#xff1a; 安装DevEco Studio 3.0或更高版本配置HarmonyOS SDK申请开发者账号 ​​项目创建​​&#xff1a; File > New > Create Project > Application (选择"Empty Ability") 二、核心功能实现 1. 医院科室展示 /…...

转转集团旗下首家二手多品类循环仓店“超级转转”开业

6月9日&#xff0c;国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解&#xff0c;“超级…...

【Linux系统】Linux环境变量:系统配置的隐形指挥官

。# Linux系列 文章目录 前言一、环境变量的概念二、常见的环境变量三、环境变量特点及其相关指令3.1 环境变量的全局性3.2、环境变量的生命周期 四、环境变量的组织方式五、C语言对环境变量的操作5.1 设置环境变量&#xff1a;setenv5.2 删除环境变量:unsetenv5.3 遍历所有环境…...

【SpringBoot自动化部署】

SpringBoot自动化部署方法 使用Jenkins进行持续集成与部署 Jenkins是最常用的自动化部署工具之一&#xff0c;能够实现代码拉取、构建、测试和部署的全流程自动化。 配置Jenkins任务时&#xff0c;需要添加Git仓库地址和凭证&#xff0c;设置构建触发器&#xff08;如GitHub…...

从物理机到云原生:全面解析计算虚拟化技术的演进与应用

前言&#xff1a;我的虚拟化技术探索之旅 我最早接触"虚拟机"的概念是从Java开始的——JVM&#xff08;Java Virtual Machine&#xff09;让"一次编写&#xff0c;到处运行"成为可能。这个软件层面的虚拟化让我着迷&#xff0c;但直到后来接触VMware和Doc…...

Windows电脑能装鸿蒙吗_Windows电脑体验鸿蒙电脑操作系统教程

鸿蒙电脑版操作系统来了&#xff0c;很多小伙伴想体验鸿蒙电脑版操作系统&#xff0c;可惜&#xff0c;鸿蒙系统并不支持你正在使用的传统的电脑来安装。不过可以通过可以使用华为官方提供的虚拟机&#xff0c;来体验大家心心念念的鸿蒙系统啦&#xff01;注意&#xff1a;虚拟…...