【leetcode面试经典150题】16.接雨水(C++)
【leetcode面试经典150题】专栏系列将为准备暑期实习生以及秋招的同学们提高在面试时的经典面试算法题的思路和想法。本专栏将以一题多解和精简算法思路为主,题解使用C++语言。(若有使用其他语言的同学也可了解题解思路,本质上语法内容一致)
【题目描述】
给定 n
个非负整数表示每个宽度为 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 个单位的雨水(蓝色部分表示雨水)。
【示例二】
输入:height = [4,2,0,3,2,5] 输出:9
【提示及数据范围】
n == height.length
1 <= n <= 2 * 10的4次方
0 <= height[i] <= 10的5次方
【代码】
// 方法一:动态规划// 对于下标 i,下雨后水能到达的最大高度等于下标 i 两边的最大高度的最小值,
// 下标 i 处能接的雨水量等于下标 i 处的水能到达的最大高度减去 height[i]。
// 创建两个长度为 n 的数组 leftMax 和 rightMax。
// 对于 0≤i<n,leftMax[i] 表示下标 i 及其左边的位置中,height 的最大高度,
// rightMax[i] 表示下标 i 及其右边的位置中,height 的最大高度。// leftMax[0]=height[0],rightMax[n−1]=height[n−1]。两个数组的其余元素的计算如下:// 当 1≤i≤n−1 时,leftMax[i]=max(leftMax[i−1],height[i]);// 当 0≤i≤n−2 时,rightMax[i]=max(rightMax[i+1],height[i])。// 因此可以正向遍历数组 height 得到数组 leftMax 的每个元素值,
// 反向遍历数组 height 得到数组 rightMax 的每个元素值。// 在得到数组 leftMax 和 rightMax 的每个元素值之后,
// 对于 0≤i<n,下标 i 处能接的雨水量等于 min(leftMax[i],rightMax[i])−height[i]。
// 遍历每个下标位置即可得到能接的雨水总量。class Solution {
public:int trap(vector<int>& height) {int n = height.size();if (n == 0) {return 0;}vector<int> leftMax(n);leftMax[0] = height[0];for (int i = 1; i < n; ++i) {leftMax[i] = max(leftMax[i - 1], height[i]);}vector<int> rightMax(n);rightMax[n - 1] = height[n - 1];for (int i = n - 2; i >= 0; --i) {rightMax[i] = max(rightMax[i + 1], height[i]);}int ans = 0;for (int i = 0; i < n; ++i) {ans += min(leftMax[i], rightMax[i]) - height[i];}return ans;}
};//方法二:单调栈// 维护一个单调栈,单调栈存储的是下标,满足从栈底到栈顶的下标对应的数组 height 中的元素递减。// 从左到右遍历数组,遍历到下标 i 时,如果栈内至少有两个元素,记栈顶元素为 top
// top 的下面一个元素是 left,则一定有 height[left]≥height[top]。// 如果 height[i]>height[top],则得到一个可以接雨水的区域,该区域的宽度是 i−left−1,
// 高度是 min(height[left],height[i])−height[top],
// 根据宽度和高度即可计算得到该区域能接的雨水量。// 为了得到 left,需要将 topp 出栈。在对 top 计算能接的雨水量之后,left 变成新的 top,
// 重复上述操作,直到栈变为空,或者栈顶下标对应的 height 中的元素大于或等于 height[i]。// 在对下标 i 处计算能接的雨水量之后,将 i 入栈,
// 继续遍历后面的下标,计算能接的雨水量。遍历结束之后即可得到能接的雨水总量。class Solution {
public:int trap(vector<int>& height) {int ans = 0;stack<int> stk;int n = height.size();for (int i = 0; i < n; ++i) {while (!stk.empty() && height[i] > height[stk.top()]) {int top = stk.top();stk.pop();if (stk.empty()) {break;}int left = stk.top();int currWidth = i - left - 1;int currHeight = min(height[left], height[i]) - height[top];ans += currWidth * currHeight;}stk.push(i);}return ans;}
};// 方法三:双指针//维护两个指针 left 和 right,以及两个变量 leftMax 和 rightMax,
// 初始时 left=0,right=n−1,leftMax=0,rightMax=0。
// 指针 left 只会向右移动,指针 right 只会向左移动,
// 在移动指针的过程中维护两个变量 leftMax 和 rightMax 的值。// 当两个指针没有相遇时,进行如下操作:// 使用 height[left] 和 height[right] 的值更新 leftMax 和 rightMax 的值;// 如果 height[left]<height[right],则必有 leftMax<rightMax,
// 下标 left 处能接的雨水量等于 leftMax−height[left] 处能接的雨水量加到能接的雨水总量,
// 然后将 left 加 1(即向右移动一位);// 如果 height[left]≥height[right],则必有 leftMax≥rightMax,
// 下标 right 处能接的雨水量等于 rightMax−height[right],
// 将下标 right 处能接的雨水量加到能接的雨水总量,然后将 right 减 1(即向左移动一位)。// 当两个指针相遇时,即可得到能接的雨水总量。class Solution {
public:int trap(vector<int>& height) {int ans = 0;int left = 0, right = height.size() - 1;int leftMax = 0, rightMax = 0;while (left < right) {leftMax = max(leftMax, height[left]);rightMax = max(rightMax, height[right]);if (height[left] < height[right]) {ans += leftMax - height[left];++left;} else {ans += rightMax - height[right];--right;}}return ans;}
};
相关文章:
【leetcode面试经典150题】16.接雨水(C++)
【leetcode面试经典150题】专栏系列将为准备暑期实习生以及秋招的同学们提高在面试时的经典面试算法题的思路和想法。本专栏将以一题多解和精简算法思路为主,题解使用C语言。(若有使用其他语言的同学也可了解题解思路,本质上语法内容一致&…...
互联网面经
腾讯视频 代码:反转链表,单例模式 RAII,哪里用到 Web服务器怎样处理请求 get\post流程 项目使用的还是http1.0吗;http2.0:二进制、首部压缩、主动推送;Https Epoll/select/poll ET/LT 进程地址空间。3…...
xss介绍及作用
XSS(Cross-Site Scripting)是一种常见的网络安全漏洞,它允许攻击者向网站注入恶意的客户端脚本代码,从而在用户的浏览器中执行这些代码。 XSS攻击的原理是攻击者将恶意脚本插入到网页中的用户输入数据中,当其他用户访…...
PostgreSQL入门到实战-第二弹
PostgreSQL入门到实战 PostgreSQL安装之Windows官网地址PostgreSQL概述Windows上安装PostgreSQL更新计划 PostgreSQL安装之Windows 官网地址 声明: 由于操作系统, 版本更新等原因, 文章所列内容不一定100%复现, 还要以官方信息为准 https://www.postgresql.org/PostgreSQL概…...
3-【PS让图片动起来】系列1-【导入素材】
【问题介绍】仅做图片,现在很难吸引用户视线,越来越多地图片需要动起来增添意境,比如春日樱花花瓣掉落、冬季雪花纷纷,今天来学学怎么用PS的时间轴,让图片动起来~ 如下图,一副冬日雪景图,想给画…...
基于Java+SpringBoot+Mybaties+layui+Vue+elememt 实习管理系统 的设计与实现
一.项目介绍 前台功能:用户进入系统可以实现首页,系统公告,个人中心,后台管理等功能进行操作 后台由管理员,实习单位,教师和学生,主要功能包括首页,个人中心,班级管理&am…...
非关系型数据库——Redis基本操作
目录 一、Redis数据库常用命令 1.Set——存放数据 2.Get——获取数据 3.Keys——获取符合条件的键值 4.Exists——判断键值是否存在 5.Del——删除指定键值 6.Type——获取键值对应的类型 7.Rename——对已有键值重命名(覆盖) 8.Renamenx——对…...
golang语言和JAVA对比
引言: 在当今的软件开发领域,有许多编程语言供开发人员选择。其中,Golang和Java是两种备受开发者青睐的语言。本文将探讨Golang和Java之间的比较和对比,分析它们在语言特性、性能、平台支持、社区和生态系统、开发效率和可维护性等方面的异同。 一、语言特性和性能 Golang…...
隐私计算实训营学习九:隐语多方安全计算在安全核对的行业实践
文章目录 一、业务背景:安全核对产生的土壤二、产品方案:从试点到规模化的路三、技术共建:与隐语的共同成长 一、业务背景:安全核对产生的土壤 业务背景:很多粗放使用数据的方式被新出台的法律法规所规范,…...
C#实现只保存2天的日志文件
文章目录 业务需求代码运行效果 欢迎讨论! 业务需求 在生产环境中,控制台窗口不便展示出来。 为了在生产环境中,完整记录控制台应用的输出,选择将其输出到文件中。 但是,存储所有输出的话会占用很多空间,…...
C++ 类和对象(中篇)
类的6个默认成员函数 如果一个类中什么成员都没有,简称为空类。空类中什么都没有吗?并不是的,任何一个类在我们不写的情 况下,都会自动生成下面6个默认成员函数。 构造函数: 定义:构造函数是一个特殊的成员…...
可视化场景(9):智慧看板,可能是最直观的数据展示
10年经验的大数据可视化和数字孪生老司机,该领域的专家,是您可信赖的技术合伙人,分享该领域的项目和作品,欢迎互动交流。 hello,我是贝格前端工场,本期分享可视化大屏在安全生产与设备运维场景的应用&#…...
加密算法(二)
1、SHA-256加密算法: package com.arithmetic.encryption; import java.security.MessageDigest; import java.security.NoSuchAlgorithmException; //使用java.security.MessageDigest类来进行SHA-256摘要的计算。 //通过getInstance("SHA-256")方法获取…...
大创项目推荐 深度学习 YOLO 实现车牌识别算法
文章目录 0 前言1 课题介绍2 算法简介2.1网络架构 3 数据准备4 模型训练5 实现效果5.1 图片识别效果5.2视频识别效果 6 部分关键代码7 最后 0 前言 🔥 优质竞赛项目系列,今天要分享的是 🚩 基于yolov5的深度学习车牌识别系统实现 该项目较…...
IP知识详解
IP基本认识 IP 在 TCP/IP 参考模型中处于第三层,也就是网络层。 网络层的主要作用是:实现主机与主机之间的通信,也叫点对点(end to end)通信。 网络层与数据链路层有什么关系呢? IP 的作用是主机之间通信…...
设计模式:适配器模式
定义 适配器模式(Adapter Pattern),也称为包装器(Wrapper)模式,是一种结构型设计模式,它允许不兼容的接口之间进行交互。适配器模式通过包装一个已有的类,提供一个与原系统兼容的接…...
大语言模型落地的关键技术:RAG
1、什么是RAG? RAG 是检索增强生成(Retrieval-Augmented Generation)的简称,是当前最火热的大语言模型应用落地的关键技术,主要用于提高语言模型的效果和准确性。它结合了两种主要的NLP方法:检索ÿ…...
ffmpeg Android 笔记
目录 没有示例项目 编译好的.a文件 ffmpegandroid 延时有220ms rk官方有例子 ffmpeg Android 笔记 没有示例项目 编译好的.a文件 FFmpeg-Android/ffmpeg-android-aarch64-34/lib at main yhbsh/FFmpeg-Android GitHub ffmpegandroid 看到了音频解码器 FFmpegAndroid/a…...
本地创建新分支并提交gitee
初始化本地仓库 git init链接远程仓库 git remote add origin https://gitee.com/xxxxxxxxxxx提交本地代码(进行commit提交) git add . git commit -m "分支名"创建分支 git branch 分支名选择刚刚创建的分支 git checkout 分支名查看所选中的分支 git branch …...
[蓝桥杯 2019 国 C] 数正方形
[蓝桥杯 2019 国 C] 数正方形 题目描述 在一个 N N N \times N NN 的点阵上,取其中 4 4 4 个点恰好组成一个正方形的 4 4 4 个顶点,一共有多少种不同的取法? 由于结果可能非常大,你只需要输出模 1 0 9 7 10^9 7 1097 的…...
Redis: 配置文件详解(Redis.conf)
文章目录 一、Units二、INCLUDES三、NETWORK四、GENERAL五、SECURITY六、LIMITS 一、Units 单位,配置大小单位,开头定义了一些基本的度量单位,只支持bytes,不支持bit,大小写不敏感 二、INCLUDES 包含,多…...
学习vue3第十四节 Teleport 内置组件介绍
<Teleport></Teleport> 作用目的: 用于将指定的组件或者元素传送到指定的位置; 通常是自定义的全局通用弹窗,绑定到 body 上,而不是在当前元素上面; 使用方法: 接收两个参数 to: 要将目标传…...
mybatis模糊查询查不到数据
排除SQL语句本身存在错误,字段名称不匹配,编码格式问题后,若使用%方式查询,一开始使用单引号查询不到数据,把改成",可以查询到数据 疑问:看别人的代码,使用单引号也可以查询到数据,原因未知...
Python语法总结:not(常出现错误)
0、not是什么 在python中not是逻辑判断词,用于布尔型True和False之前 a not Ture # a False b not False # b True1、not的用法 (1)判断语句 if not a:# 如果a是False,执行的语句(2)判断元素是否在…...
深入理解WebSocket:实时双向通信的利器
一、介绍 1.1 基础概念介绍 单工通信:数据传输只允许在一个方向上传输,只能一方发送数据,另一方接收数据并发送。半双工:数据传输允许两个方向上的传输,但在同一时间内,只可以有一方发送或接收数据。全双…...
Gateway是什么?(SpringCloudAlibaba组件)
1、网关介绍 **网关(Gateway)又称网间连接器、协议转换器。网关在传输层上以实现网络互连,是最复杂的网络互连设备,仅用于两个高层协议不同的网络互连。**网关的结构也和路由器类似,不同的是互连层。网关既可以用于广域网互连,也可…...
阿里巴巴拍立淘API新功能揭秘:图片秒搜商品,实现智能化个性化购物新体验
在数字化快速发展的今天,智能化和个性化已经成为购物体验中不可或缺的元素。为了满足消费者日益增长的购物需求,阿里巴巴中国站不断推陈出新,其中拍立淘API的新功能——图片秒搜商品,无疑为智能化个性化购物体验开创了新的篇章。 …...
蚓链为移动实体经济加油!
在当今数字化时代,数据已成为企业宝贵的资产之一。如何利用数据资产为可移动实体经济创造更多的增值机会呢?蚓链将为你揭示 11种行之有效的方法! 1. 个性化服务:根据客户数据,提供量身定制的产品和服务,满…...
MySQL 核心模块揭秘 | 12 期 | 创建 savepoint
回滚操作,除了回滚整个事务,还可以部分回滚。部分回滚,需要保存点(savepoint)的协助。本文我们先看看保存点里面都有什么。 作者:操盛春,爱可生技术专家,公众号『一树一溪』作者&…...
SpringMVC --- 老杜
1、什么是SpringMVC? SpringMVC是一个基于Java实现了MVC设计模式的请求驱动类型的轻量级Web框架,通过把Model,View,Controller分离,将web层进行职责解耦,把复杂的web应用分成逻辑清晰的及部分,…...
请私人做网站风险/新开发的app怎么推广
FER转载于:https://www.cnblogs.com/hengguangliu/p/5994093.html...
没有网站如何做天天联盟/软件开发外包公司
为什么80%的码农都做不了架构师?>>> 作为他的忠实粉丝,决定从今天开始,看到他的每一句经典的、有价值的、令人回味深长的话,都记录下来,以便反复学习。 问:学习设计模式有什么好书推荐&#x…...
网站开发顶岗实习报告/小广告怎么能弄干净
不知道为什么自己突然想把一切都写下来,或许对她的爱是那么的深,永远都不想忘记。Msn突然亮了,兴奋的点开,发现她发来的信息,“不知道咱们怎么继续下去了”。一句话验证了我多日的困扰,她又说出这种话了&am…...
到位app做网站需要些程序/万网域名注册查询
1、model转json # model转json字典 def serialize(model):columns [c.key for c in class_mapper(model.__class__).columns]data dict()for c in columns:v getattr(model, c)if type(v) datetime: # 日期类型在转json字符时会出错,所以需要提前格式化v date…...
广南网站建设/怎样在百度上发布自己的信息
买了这本书,想着边看边整理一下,可以方便以后查阅。分享出来,大家都可以看看!第3章 使用MySQL 使用数据库 —— USE 数据库名称了解数据库 —— SHOW 数据库名称查看数据库中的表 —— SHOW TABLES 查看表中列的消息 —— SHOW CO…...
一百度网站建设/产品推广的渠道有哪些
1.JAVA循环控制...