接雨水
接雨水
- 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 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。 2、解题思路 本题使用了双指针,根据下图可以得出,下标 i 处能接的雨水量由左边…...
Python蓝桥杯刷题1
1.确定字符串是否包含唯一字符 题解:调用count函数计算每一个字符出现的次数,如果不等于1就输出no,并且结束循环,如果等于1就一直循环直到计算到最后一个字符,若最后一个字符也满足条件,则输出yes import…...
实习冲刺第二十七天
3.无重复字符的最长字串 给定一个字符串 s ,请你找出其中不含有重复字符的 最长 子串 的长度。 示例 1: 输入: s "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。示例 2: 输入: s "bbbb…...
el-table-column自动生成序号在序号前插入图标
实现效果: 代码如下: 在el-table里加入这个就可以了,需要拿到值可以用scope.$index <el-table-column type"index" label"序号" show-overflow-tooltip"true" min-width"40">…...
前端工程化-node/npm/babel/polyfill/webpack 一文速通
文章主要介绍了前端工程化的相关内容,包括 Node 环境、npm 包管理器及其命令、配置和镜像,package.json 文件,babel 和 polyfill 用于解决 JavaScript 兼容性问题,以及 webpack 这一前端构建工具的作用、核心概念、构建流程、安装…...
Spring Security PasswordEncoder接口(密码编码)
密码编码(通常称为哈希)是一种安全措施,它将明文密码转换为独特的字符字符串。 主要目的是确保即使数据存储遭到破坏,存储的密码也不会轻易被破解。 与加密不同,哈希是一个单向过程——这意味着无法从哈希值中恢复原…...
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,1GB内存,是新一代开拓者,兼容1代B。相比之下,树莓派2的性能比1代提升6倍,内存翻了一番。Raspberry Pi 2不仅能跑全系列ARM GNU/Linux发行版,而且支…...
探索C/C++的奥秘之stack和queue
1. stack的介绍和使用 1.1 stack的介绍 1. stack是一种容器适配器,专门用在具有后进先出操作的上下文环境中,其删除只能从容器的一端进行元素的插入与提取操作。具体什么是适配器呢?其实就是由现有的东西进行转换,转化出我要的东…...
[开源]1.2K star!中后台方向的低代码可视化平台,超赞!
大家好,我是JavaCodexPro! “时间就是金钱,效率就是生命”,快速搭建高质量中后台的低代码可视化搭建平台尤为重要! 今天JavaCodexPro给大家分享一款超赞的低代码可视化搭建平台 - Marsview ,旨在简化开发…...
算法编程题-排序
算法编程题-排序 比较型排序算法冒泡排序选择排序插入排序希尔排序堆排序快速排序归并排序 非比较型排序算法计数排序基数排序 本文将对七中经典比较型排序算法进行介绍,并且给出golang语言的实现,还包括基数排序、计数排序等非比较型的算法的介绍和实现…...
【AIGC】如何准确引导ChatGPT,实现精细化GPTs指令生成
博客主页: [小ᶻZ࿆] 本文专栏: AIGC | 提示词Prompt应用实例 文章目录 💯前言💯准确引导ChatGPT创建爆款小红书文案GPTs指令案例💯 高效开发GPTs应用的核心原则明确应用场景和目标受众构建多样化风格模板提问与引导技巧持续优…...
【Axure高保真原型】或和且条件
今天和大家分享或和且条件案例的原型模板,效果包括: 可以选择指标、等式和填写对应值构成条件等式; 点击添加条件按钮,可以增加一行新的条件; 点击所在行的号按钮,可以在该行下方添加一行新的条件&#x…...
KubeVirt下gpu operator实践(GPU直通)
KubeVirt下gpu operator实践(GPU直通) 参考《在 KubeVirt 中使用 GPU Operator》,记录gpu operator在KubeVirt下实践的过程,包括虚拟机配置GPU直通,容器挂载GPU设备等。 KubeVirt 提供了一种将主机设备分配给虚拟机的机制。该机制具有通用性…...
Vue通过file控件上传文件到Node服务器
功能: 1.多文件同时上传、2.拖动上传、3.实时上传进度条、4.中断上传和删除文件、5.原生file控件的美化 搁置的功能: 上传文件夹、大文件切片上传、以及其他限制条件未处理 Node服务器的前置准备: 新建文件夹: file_upload_serve初始化npm: npm …...
如何在 SQL Server 中新增账户并指定数据库权限
在日常的数据库维护与开发中,管理用户的权限是必不可少的一环。本文将指导你如何在 SQL Server 中为新用户创建账户,并为其指定相应的数据库权限,使其只能查看有权访问的数据。我们将以步骤和代码示例的方式展示整个流程。用户权限分配包括:读取权限、写入权限、执行权限。…...
c#编码技巧(十九):各种集合特点汇总
.NET 常用集合对比: .NET 常见的线程安全集合 .NET 只读集合...
汽车软件DevOps解决方案
汽车软件DevOps解决方案是专为现代汽车行业设计的一套集成化需求、开发、测试、部署、OTA与监控,旨在加速软件开发流程,提高软件质量和安全性,同时确保整个生命周期的高效性和灵活性。以下是经纬恒润汽车软件DevOps解决方案的关键组成部分和优…...
同步的意义以及机制
一、同步的意义 同步(Synchronization)的意义在于确保在多线程环境中,多个线程对共享资源的访问是安全的,避免竞争条件(race conditions)和数据不一致的情况。 具体来说,同步的核心目标是&…...
leetcode 面试150之 156.LUR 缓存
请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。 实现 LRUCache 类: LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -…...
eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)
说明: 想象一下,你正在用eNSP搭建一个虚拟的网络世界,里面有虚拟的路由器、交换机、电脑(PC)等等。这些设备都在你的电脑里面“运行”,它们之间可以互相通信,就像一个封闭的小王国。 但是&#…...
遍历 Map 类型集合的方法汇总
1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...
Spring AI与Spring Modulith核心技术解析
Spring AI核心架构解析 Spring AI(https://spring.io/projects/spring-ai)作为Spring生态中的AI集成框架,其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似,但特别为多语…...
优选算法第十二讲:队列 + 宽搜 优先级队列
优选算法第十二讲:队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...
python执行测试用例,allure报乱码且未成功生成报告
allure执行测试用例时显示乱码:‘allure’ �����ڲ����ⲿ���Ҳ���ǿ�&am…...
【Go语言基础【13】】函数、闭包、方法
文章目录 零、概述一、函数基础1、函数基础概念2、参数传递机制3、返回值特性3.1. 多返回值3.2. 命名返回值3.3. 错误处理 二、函数类型与高阶函数1. 函数类型定义2. 高阶函数(函数作为参数、返回值) 三、匿名函数与闭包1. 匿名函数(Lambda函…...
在Mathematica中实现Newton-Raphson迭代的收敛时间算法(一般三次多项式)
考察一般的三次多项式,以r为参数: p[z_, r_] : z^3 (r - 1) z - r; roots[r_] : z /. Solve[p[z, r] 0, z]; 此多项式的根为: 尽管看起来这个多项式是特殊的,其实一般的三次多项式都是可以通过线性变换化为这个形式…...
4. TypeScript 类型推断与类型组合
一、类型推断 (一) 什么是类型推断 TypeScript 的类型推断会根据变量、函数返回值、对象和数组的赋值和使用方式,自动确定它们的类型。 这一特性减少了显式类型注解的需要,在保持类型安全的同时简化了代码。通过分析上下文和初始值,TypeSc…...
《Docker》架构
文章目录 架构模式单机架构应用数据分离架构应用服务器集群架构读写分离/主从分离架构冷热分离架构垂直分库架构微服务架构容器编排架构什么是容器,docker,镜像,k8s 架构模式 单机架构 单机架构其实就是应用服务器和单机服务器都部署在同一…...
消防一体化安全管控平台:构建消防“一张图”和APP统一管理
在城市的某个角落,一场突如其来的火灾打破了平静。熊熊烈火迅速蔓延,滚滚浓烟弥漫开来,周围群众的生命财产安全受到严重威胁。就在这千钧一发之际,消防救援队伍迅速行动,而豪越科技消防一体化安全管控平台构建的消防“…...
