LeetCode 接雨水 双指针

原题链接:

力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

题面:

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

示例 1:

输入:height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出:6
解释:上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。 

示例 2:

输入:height = [4,2,0,3,2,5]
输出:9

提示:

  • n == height.length
  • 1 <= n <= 2 * 10^4
  • 0 <= height[i] <= 10^5

解题思路:

由木桶理论可知某一列的储水量与他左边最高的柱子和右边最高的柱子之间的较矮者有关,为这一列高度和它的差值。在上一篇博客,我们使用了DP方法,维护了两个数组left和right,空间复杂度为O(n),但实际上我们可以使用双指针法,空间复杂度可以优化到O(1)。

设左指针left,右指针right,当left和right未相遇时,维护leftMax和rightMax,左指针left只从左往右,右指针right只从右往左,leftMax = max(leftMax, height[left]),rightMax = max(rightMax, height[right])。

当leftMax < rightMax时,我们可以计算出left位置的储水量为leftMax - height[left],并将left右移一位;

当leftMax > rightMax时,我们可以计算出right位置的储水量为rightMax - height[right],并将right左移一位;

当leftMax == rightMax时,无论对left操作还是对right操作都是可以的。

当left和right相遇时,就可以结束计算了。

代码(CPP):

class Solution {
public:/*双指针,将空间复杂度从O(n)优化至O(1)*/int trap(vector<int>& height) {int n = height.size();int left = 0, right = n - 1;int leftMax = 0, rightMax = 0, ans = 0;while (left < right) {leftMax = max(leftMax, height[left]);rightMax = max(rightMax, height[right]);if (leftMax < rightMax) {ans += leftMax - height[left];left++;} else {ans += rightMax - height[right];right--;}}return ans;}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/142627.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

CSS实现围绕按钮边框转圈的光线效果

CSS实现围绕按钮边框转圈的光线效果&#xff0c;可以自由改变按钮的光线渐变颜色和按钮边框颜色&#xff0c;背景色等。 效果图&#xff1a; 实现完整代码&#xff1a; <template><view class"btnBlock"><view class"btnBian"></vi…

win11怎么查看之前连过的wifi密码

首先进入到设置 然后就可以看到之前连接过的WIFI&#xff1a; 选一个想要知道密码的WIFI点进去看到如下页面&#xff1a; 然后点击“显示”即可查看密码

Redis 数据类型底层原理

String 内部编码有三种&#xff1a;int、embstr、raw int&#xff1a;如果一个字符串对象保存的是整数值&#xff0c;并且这个整数值可以用 long类型来表示(不超过 long 的表示范围&#xff0c;如果超过了 long 的表示范围&#xff0c;那么按照存储字符串的编码来存储&#xf…

kafka安装部署,和基本操作

kafka下载地址&#xff1a;Apache Kafka 我这里下载3.5.1 ​ 2、通过rz命令上传到linux服务器 3、解压 tar -zxvf kafka_2.12-3.5.1.tgz 4、在config目录下修改配置文件server.properties 主要修改这两处&#xff1a; #监听的端口advertised.listenersPLAINTEXT://自己…

java spring cloud 企业电子招标采购系统源码:营造全面规范安全的电子招投标环境,促进招投标市场健康可持续发展

功能描述 1、门户管理&#xff1a;所有用户可在门户页面查看所有的公告信息及相关的通知信息。主要板块包含&#xff1a;招标公告、非招标公告、系统通知、政策法规。 2、立项管理&#xff1a;企业用户可对需要采购的项目进行立项申请&#xff0c;并提交审批&#xff0c;查看所…

uniapp实现表格冻结

效果图如下&#xff1a; 思路&#xff1a; 1.由于APP项目需要&#xff0c;起初想去插件市场直接找现成的&#xff0c;结果找了很久没找到合适的&#xff08;有的不支持vue2有的不能都支持APP和小程序&#xff09; 2.后来&#xff0c;就只能去改uni-table源码了&#xff0c;因…

【面试高高手】——Spring(12题)

文章目录 1.Spring是什么&#xff1f;2.为什么需要Spring?3.说下你对Spring的AOP、IOC的理解&#xff1f;4.基于java的AOP实现有哪些&#xff1f;5.AOP的原理&#xff1f;6.如何使用Java实现动态代理?7. Spring AOP和AspectJ AOP有什么区别&#xff1f;8.SpringAOP通知类型&a…

联想详解AI导向基础设施 “软硬一体”赋能四大场景

9月25日&#xff0c;联想在杭州举办以“全栈智能 全程陪伴”为主题的新IT思享会&#xff0c;集中展示了联想基于新IT架构的全栈智能产品与服务&#xff0c;引领行业智能变革的强大实力。 当前&#xff0c;以ChatGPT为代表的AI模型席卷全球&#xff0c;不仅实现了AI技术质变性突…

电路常见的通信接口

1,TTL/232/485/422简介 串口 串口通信(Serial Communication)&#xff0c; 是指外设和计算机间&#xff0c;通过数据信号线 、地线、控制线等&#xff0c;按位进行传输数据的一种通讯方式。是我们在硬件调试过程中最常见的一种通信方式。比如开发板和电脑之间&#xff0c;想要…

如何更改注册表使系统暂停更新时间延长

1、创建一个文本文件&#xff0c;命名为&#xff1a;“stopupdate.reg”&#xff0c;然后用记事本或者代码编辑器打开&#xff0c;复制以下代码&#xff1a; Windows Registry Editor Version 5.00[HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\WindowsUpdate\UX\Settings] "F…

高手必备!电脑剪辑视频的实用方法

随着数码时代的到来&#xff0c;越来越多的人开始使用电脑剪辑视频。电脑剪辑视频不仅可以为日常生活留下美好回忆&#xff0c;还可以为专业人士提供更多的创作可能性。在本文中&#xff0c;我们将介绍两种电脑剪辑视频的方法&#xff0c;不需要专业技能&#xff0c;只需要一台…

嵌入式MCU都有什么高级用法?

嵌入式MCU都有什么高级用法&#xff1f; 您举的几个例子&#xff0c;确实是MCU外设的一些高端玩法。只是不知道您是否想过&#xff0c;既然这些机制是被 人设计出来的&#xff0c;那它就是种标准用法。从微控制器的发展历程来看&#xff0c;许多硬件机制都是有了实际 需求后才…

工业RFID识别设备可以在哪些行业应用?

工业识别设备主要是用于工业领域的RFID读写设备&#xff0c;它可以在产线、工厂、仓储物流等领域应用&#xff0c;非接触的实时读取标签信息&#xff0c;并且将读取的信息上传到电脑信息管理系统中。 工业RFID识别设备可以在哪些行业应用? 1、汽车行业 汽车制造业的产品结构复…

USB转换方案介绍

随着科技的不断发展&#xff0c;我们的生活中出现了越来越多的电子设备。然而&#xff0c;这些设备通常具有不同的连接端口和协议&#xff0c;这可能会使它们之间的连接变得困难。这时候&#xff0c;使用USB转换就成为了一种非常方便和实用的解决方法。 无论是在家庭、办公室还…

网络编程day03(UDP中的connect函数、tftp)

今日任务&#xff1a;tftp的文件上传下载&#xff08;服务端已经准备好&#xff09; 服务端&#xff08;已上传&#xff09; 客户端&#xff1a; 代码&#xff1a; #include <stdio.h> #include <string.h> #include <stdlib.h> #include <sys/types.h…

vue实现进度条+背景定位

最近在做一个数字孪生项目&#xff0c;用于展示地铁车辆的进场动画及部件&#xff0c;使用的vueunity&#xff0c;但是 unity模型在加载完成之前会有个加载进度条&#xff0c;页面背景色是黑色&#xff0c;中间只有个一进度条框 可以看到很单调很丑&#xff0c;并且客户也不满…

Linux上的Pip和Python升级指南

在Linux系统上&#xff0c;保持Pip和Python版本的最新状态对于顺利进行Python开发至关重要。通过升级Pip和Python&#xff0c;你可以享受到最新的功能、修复的bug以及提升的开发效率。本文将为你提供在Linux上升级Pip和Python的详细指南&#xff0c;助你打造更强大的开发环境。…

✔ ★ 算法基础笔记(Acwing)(六)—— 贪心【java版本】

贪心 一、 区间问题1. 区间选点2. 最大不相交区间数量3. 区间分组(用 堆top 代表区间 头头)POJ3614Sunscreen(优先队列贪心) 4. 区间覆盖 二、哈夫曼树1. 合并果子 三、排序不等式1. 排队打水 四、绝对值不等式货仓选址 五、推公式耍杂技的牛 一、 区间问题 1. 区间选点 原题…

气传导和骨传导耳机哪个好?气传导耳机好用吗?气传导耳机推荐

​气传导和骨传导耳机都是不入耳设计&#xff0c;骨传导是通过振动颅骨传达声音信号 骨传导耳机是一种能够通过振动颅骨来传达声音信号的耳机&#xff0c;其原理是利用骨传导技术&#xff0c;将声音信号通过颅骨传达到内耳&#xff0c;从而实现听觉效果&#xff0c;不过长时间佩…

YashanDB向量化执行引擎如何给海量数据分析提速

作者介绍&#xff1a;李伟超&#xff0c;数据库系统架构师&#xff0c;YashanDB架设技术开发负责人&#xff0c;10年以上数据库内核技术开发经验。 *全文4510个字&#xff0c;阅读时长约11分钟。 背景 海量数据OLAP场景&#xff0c;通常具有数据规模大、查询复杂度高、处理速…