接雨水
接雨水
- 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 存在于缓存中,则返回关键字的值,否则返回 -…...
【Axure高保真原型】引导弹窗
今天和大家中分享引导弹窗的原型模板,载入页面后,会显示引导弹窗,适用于引导用户使用页面,点击完成后,会显示下一个引导弹窗,直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...
Linux应用开发之网络套接字编程(实例篇)
服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...
Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)
目录 1.TCP的连接管理机制(1)三次握手①握手过程②对握手过程的理解 (2)四次挥手(3)握手和挥手的触发(4)状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...
dedecms 织梦自定义表单留言增加ajax验证码功能
增加ajax功能模块,用户不点击提交按钮,只要输入框失去焦点,就会提前提示验证码是否正确。 一,模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...
渲染学进阶内容——模型
最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...
Keil 中设置 STM32 Flash 和 RAM 地址详解
文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...
如何将联系人从 iPhone 转移到 Android
从 iPhone 换到 Android 手机时,你可能需要保留重要的数据,例如通讯录。好在,将通讯录从 iPhone 转移到 Android 手机非常简单,你可以从本文中学习 6 种可靠的方法,确保随时保持连接,不错过任何信息。 第 1…...
RSS 2025|从说明书学习复杂机器人操作任务:NUS邵林团队提出全新机器人装配技能学习框架Manual2Skill
视觉语言模型(Vision-Language Models, VLMs),为真实环境中的机器人操作任务提供了极具潜力的解决方案。 尽管 VLMs 取得了显著进展,机器人仍难以胜任复杂的长时程任务(如家具装配),主要受限于人…...
Python+ZeroMQ实战:智能车辆状态监控与模拟模式自动切换
目录 关键点 技术实现1 技术实现2 摘要: 本文将介绍如何利用Python和ZeroMQ消息队列构建一个智能车辆状态监控系统。系统能够根据时间策略自动切换驾驶模式(自动驾驶、人工驾驶、远程驾驶、主动安全),并通过实时消息推送更新车…...
Chrome 浏览器前端与客户端双向通信实战
Chrome 前端(即页面 JS / Web UI)与客户端(C 后端)的交互机制,是 Chromium 架构中非常核心的一环。下面我将按常见场景,从通道、流程、技术栈几个角度做一套完整的分析,特别适合你这种在分析和改…...
