leetcode 42. 接雨水

2023.8.29

         本题可以用双指针做,求出每一列能盛的雨水,再相加即可。不过暴力法会超时,需要优化。

双指针(暴力):

class Solution {
public:int trap(vector<int>& height) {int ans = 0;for(int i=1; i<height.size()-1; i++){int max_rheight = height[i]; //记录当前柱子右边的最高柱子int max_lheight = height[i]; //记录当前柱子左边的最高柱子for(int r=i+1; r<height.size(); r++){max_rheight = max(max_rheight,height[r]);}for(int l=i-1; l>=0; l--){max_lheight = max(max_lheight,height[l]);}ans += max(0 , min(max_rheight,max_lheight)-height[i]);}return ans;}
};

双指针(优化):

        上面双指针暴力法每次遍历都需要求一次当前柱子左右两侧的最高柱子,这样有重复,自然会超时。 优化办法是设置两个数组left和right,分别存储每一个柱子的左侧最高柱子,及右侧最高柱子,这样子就不用重复遍历了。 代码如下:

class Solution {
public:int trap(vector<int>& height) {//求出当前柱子的左侧最高柱子以及右侧最高柱子,保存在两数组中。vector<int> left(height.size());vector<int> right(height.size());int max_lheight = height[0];int max_rheight = height[height.size()-1];for(int i=1; i<left.size()-1; i++){left[i] = max_lheight;max_lheight = max(max_lheight,height[i]);}for(int i=right.size()-2; i>=1; i--){right[i] = max_rheight;max_rheight = max(max_rheight,height[i]);}//遍历每一列求出最大雨水int ans = 0;for(int i=1; i<height.size()-1; i++){ans += max(0 , min(left[i],right[i])-height[i]);}return ans;}
};

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

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

相关文章

(牛客周赛 9)C.小美的01串翻转

题目&#xff1a; 样例&#xff1a; 输入 10001 输出 8 思路&#xff1a; 这里是连续的找子串&#xff0c;权值的意思是 我们取反操作了多少次&#xff0c; 我们有假设长度是 5 &#xff0c;字符串是 10001 那么相邻不一样的字符串有两种情况 01010 或者 10101&#xf…

高等职业学校物联网实训室建设方案

一、概述 1.1专业背景 物联网&#xff08;Internet of Things&#xff09;被称为继计算机、互联网之后世界信息产业第三次浪潮&#xff0c;它并非一个全新的技术领域&#xff0c;而是现代信息技术发展到一定阶段后出现的一种聚合性应用与技术提升&#xff0c;是随着传感网、通…

耐世特Nexteer EDI解决方案

耐世特Nexteer曾经为美国通用汽车全资子公司&#xff0c;是一家集研发、制造、销售于一体的全球化集团公司。耐世特汽车系统公司是转向系统及相关先进技术的全球供应商。该公司为60多家汽车制造商设计、制造、销售电动助力转向器、液压助力转向器、转向管柱和传动轴产品&#x…

GNU make系列之写Makefile文件(1)

一.欢迎来到我的酒馆 在本章节介绍如何写Makefile文件。 目录 一.欢迎来到我的酒馆二.Makefile包含了什么三.引入其它的Makefile文件四.MAKEFILES变量 二.Makefile包含了什么 2.1 Makefile包含了5种类型&#xff1a;显式的规则&#xff0c;隐式的规则&#xff0c;变量的定义&am…

数据结构:八种数据结构大全

数据结构 1.1 数据结构概述 数据结构是计算机存储、组织数据的方式&#xff1b;通常情况下&#xff0c;精心选择的数据结构可以带来更高的运行或者存储效率。数据结构的优良将直接影响着我们程序的性能&#xff1b;常用的数据结构有&#xff1a;数组&#xff08;Array&#xff…

【Qt学习】05:自定义封装界面类

OVERVIEW 自定义封装界面类1.QListWidget2.QTreeWidget3.QTableWidget4.StackedWidget5.Others6.自定义封装界面类-显示效果&#xff08;1&#xff09;添加设计师界面类&#xff08;2&#xff09;在ui中设计自定义界面&#xff08;3&#xff09;在需要使用的界面中添加&#xf…

面试题(三)

目录 一.Spring 1.Spring IOC & AOP 2.Spring bean (1) 作用域 (2) Spring 中的 bean ⽣命周期 (3) Spring 框架中⽤到了哪些设计模式 二.Mybatis 1.标签 2.Dao接口 3.返回与映射 4.延迟加载 三.Kafka 四.设计模式 1.IO 设计模式 2.Spring 中的设计模式详解…

【前端】常用功能合集

目录 js跳转到新标签打开PDF文件js每十个字符换行 es6用表达式或变量名作为对象的属性名 vuev-for插值、:style、:class父组件加载完后再加载子组件keep-alive缓存跨域请求第三方接口跨域请求之callback&#xff08;不建议&#xff09;读取本地文件浏览器播放提示音audio jquer…

Lora升级!ReLoRa!最新论文 High-Rank Training Through Low-Rank Updates

目录 摘要1 引言2 相关工作3 方法4 实验5 结果6 结论7 局限性和未来工作 关注公众号TechLead&#xff0c;分享AI与云服务技术的全维度知识。作者拥有10年互联网服务架构、AI产品研发经验、团队管理经验&#xff0c;同济本复旦硕&#xff0c;复旦机器人智能实验室成员&#xff0…

1、[春秋云镜]CVE-2022-32991

文章目录 一、相关信息二、解题思路&#xff08;手注&#xff09;三、通关思路&#xff08;sqlmap&#xff09; 一、相关信息 靶场提示&#xff1a;该CMS的welcome.php中存在SQL注入攻击。 NVD关于漏洞的描述&#xff1a; 注入点不仅在eid处&#xff01;&#xff01;&#xff…

路由器的简单概述(详细理解+实例精讲)

系列文章目录 华为数通学习&#xff08;4&#xff09; 目录 系列文章目录 华为数通学习&#xff08;4&#xff09; 前言 一&#xff0c;网段间通信 二&#xff0c;路由器的基本特点 三&#xff0c;路由信息介绍 四&#xff0c;路由表 五&#xff0c;路由表的来源有哪些…

新能源汽车动力总成系统及技术

需要动力系统总成的请联&#xff1a;shbinzer 拆车邦 需要动力系统总成的请联&#xff1a;shbinzer 拆车邦 需要动力系统总成的请联&#xff1a;shbinzer 拆车邦 需要动力系统总成的请联&#xff1a;shbinzer 拆车邦 需要动力系统总成的请联&#xff1a;shbinzer …

k3s or RKE2 helm安装报错dial tcp 127.0.0.1:8080: connect: connection refused

1.报错&#xff1a; Error: INSTALLATION FAILED: Kubernetes cluster unreachable: Get "http://127.0.0.1:8080/version": dial tcp 127.0.0.1:8080: connect: connection refused 2.问题原因&#xff1a; 1.因为helm默认使用k8s的配置文件&#xff0c;默…

uniapp 配置网络请求并使用请求轮播图

由于平台的限制&#xff0c;小程序项目中不支持 axios&#xff0c;而且原生的 wx.request() API 功能较为简单&#xff0c;不支持拦截器等全局定制的功能。因此&#xff0c;建议在 uni-app 项目中使用 escook/request-miniprogram 第三方包发起网络数据请求。 官方文档&#xf…

宏观经济和风电预测误差分析(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…

springboot1.5.12升级至2.6.15

首先&#xff0c;加入springboot升级大版本依赖&#xff0c;会在升级过程中打印出错日志提示&#xff08;升级完毕可去除&#xff09; <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-properties-migrator</art…

基于龙格-库塔算法优化的BP神经网络(预测应用) - 附代码

基于龙格-库塔算法优化的BP神经网络&#xff08;预测应用&#xff09; - 附代码 文章目录 基于龙格-库塔算法优化的BP神经网络&#xff08;预测应用&#xff09; - 附代码1.数据介绍2.龙格-库塔优化BP神经网络2.1 BP神经网络参数设置2.2 龙格-库塔算法应用 4.测试结果&#xff…

The Cherno——OpenGL

The Cherno——OpenGL 1. 欢迎来到OpenGL OpenGL是一种跨平台的图形接口&#xff08;API&#xff09;&#xff0c;就是一大堆我们能够调用的函数去做一些与图像相关的事情。特殊的是&#xff0c;OpenGL允许我们访问GPU&#xff08;Graphics Processing Unit 图像处理单元&…

C++异常

文章目录 C异常异常语法代码示例 栈解旋示例代码 noexcept代码示例 异常的声明周期示例代码 异常的多态使用代码示例 C标准异常库代码示例 重写自己的异常示例代码 C异常 异常是处理程序中的错误。所谓的错误时指程序运行的过程中发生的一些异常事件(如&#xff1a;除零错误&a…

jenkins运行pytest测试用例脚本报错:没有权限,无法写日志PermissionError:[Error 13]Permission denied

报错信息&#xff1a; PermissionError:[Error 13]Permission denied&#xff1a;‘/var/jenkins_home/workspace/deleverySystem/Delivery_System/out_files/logs/waimai_20230823.log’ 解决方法&#xff1a; 在jenkins容器内部输入 chmod -R 777 /var/jenkins_home/works…