当前位置: 首页 > news >正文

单调栈day54|42. 接雨水(高频面试题)、84. 柱状图中最大的矩形、两道题思维导图的汇总与对比

单调栈day54|42. 接雨水(高频面试题)、84. 柱状图中最大的矩形、两道题思维导图的汇总与对比

  • 42. 接雨水
  • 84. 柱状图中最大的矩形
  • 两道题思维导图的汇总与对比

42. 接雨水

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

示例 1:

img

输入: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 * 104
  • 0 <= height[i] <= 105
class Solution {
public:int trap(vector<int>& height) {int sum=0;stack<int> st;st.push(0);for(int i=1;i<height.size();i++){if(height[i]<=height[st.top()])st.push(i);else{while(!st.empty()&&height[i]>height[st.top()]){int mid=height[st.top()];st.pop();if(!st.empty()){int h=min(height[st.top()],height[i])-mid;int w=i-st.top()-1;sum+=h*w;}}st.push(i);}}return sum;}
};

具体的分析过程如下面的思维导图所示:
在这里插入图片描述

84. 柱状图中最大的矩形

给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。

求在该柱状图中,能够勾勒出来的矩形的最大面积。

示例 1:

在这里插入图片描述

输入:heights = [2,1,5,6,2,3]
输出:10
解释:最大的矩形为图中红色区域,面积为 10

提示:

  • 1 <= heights.length <=105
  • 0 <= heights[i] <= 104
class Solution {
public:int largestRectangleArea(vector<int>& heights) {stack<int> st;int result=0;heights.insert(heights.begin(),0);heights.push_back(0);st.push(0);for(int i=0;i<heights.size();i++){if(heights[i]>=heights[st.top()])st.push(i);else{while(!st.empty()&&heights[i]<heights[st.top()]){int mid=st.top();st.pop();if(!st.empty()){int h=heights[mid];int w=i-st.top()-1;result=max(result,h*w);}}st.push(i);}}return result;}
};

具体的分析过程如下面的思维导图所示:
在这里插入图片描述

两道题思维导图的汇总与对比

在这里插入图片描述

相关文章:

单调栈day54|42. 接雨水(高频面试题)、84. 柱状图中最大的矩形、两道题思维导图的汇总与对比

单调栈day54|42. 接雨水&#xff08;高频面试题&#xff09;、84. 柱状图中最大的矩形、两道题思维导图的汇总与对比 42. 接雨水84. 柱状图中最大的矩形两道题思维导图的汇总与对比 42. 接雨水 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图&#xff0c;计算按此排列的柱…...

关于Excel将列号由字母改为数字

将Excel的列表由字母改为数字 步骤&#xff1a; 文件-选项-公式-勾选“使用公式”中的“R1C1引用样式(R)”-确定即可 部分步骤图示 设置前的样子 设置后的样子 虽然现在还不清楚在xlwings操作Excel时有什么作用&#xff0c;先留着吧。...

曾黎第二次受邀巴黎时装周看秀 为新疆棉代言引人瞩目

近日&#xff0c;演员曾黎受邀出席巴黎时装周Stella McCartney 2025春夏大秀&#xff0c;她身穿品牌25早春“超季”新装登场&#xff0c;干练的摩登蓝色西服&#xff0c;自信优雅&#xff0c;温婉大气&#xff0c;手提链条黑包上面绑着的一朵新疆棉花十分抢眼&#xff0c;成为全…...

No.6 笔记 | Linux操作系统基础:全面概览与核心要点

1. 简介与历史 1.1 起源 创始人&#xff1a;Linus Torvalds&#xff08;芬兰赫尔辛基大学学生&#xff09;初衷&#xff1a;设计一个替代Minix的全功能Unix操作系统首次发布&#xff1a;1991年10月5日&#xff0c;Linux v0.01版本 2. Linux特点 多用户多任务&#xff1a;用…...

MySQL之分库分表后带来的“副作用”你是怎么解决的?

目录标题 一、垂直分表后带来的隐患二、水平分表后带来的问题1.多表联查问题2.增删改数据问题3.聚合操作问题 三、垂直分库后产生的问题1.跨库join问题2.分布式事务问题3.部分业务库依然存在的性能问题 四、水平分库后需要解决的问题1.聚合操作和连表问题2.数据分页问题3.ID主键…...

【Python】Python-JOSE:Python 中的 JSON Web Token 处理库

Python-JOSE 是一个用于处理 JSON Web Token (JWT) 和 JOSE (JSON Object Signing and Encryption) 标准的 Python 库。它支持对 JWT 进行签名、加密、解密和验证等操作&#xff0c;是处理基于 OAuth 2.0 和 OpenID Connect 协议的身份验证和授权任务的理想选择。Python-JOSE 实…...

SpringBoot3+Druid YAML配置

背景 Druid连接池是阿里巴巴开源的数据库连接池项目。Druid连接池为监控而生&#xff0c;内置强大的监控功能&#xff0c;监控特性不影响性能。功能强大&#xff0c;能防SQL注入&#xff0c;内置Loging能诊断Hack应用行为。现在已经SpringBoot3&#xff0c;Druid的配置也需要随…...

【c语言——指针详解(3)】

文章目录 一、字符指针变量二、数组指针变量1、 数组指针变量是什么&#xff1f;2、 数组指针变量怎么初始化 三、⼆维数组传参的本质四、函数指针变量1、函数指针变量的创建2、函数指针变量的使⽤3、两段有趣的代码1&#xff09;typedef 关键字2&#xff09;typedef和define的…...

QT系统学习篇(2)- Qt跨平台GUI原理机制

一、Qt工程管理 1、新建项目&#xff1a; 我们程序员新建项目对话框所有5类项目模板 Application: Qt的应用程序&#xff0c;包含Qt Quick和普通窗口程序。 Library: 它可以创建动态库、静态库、Qt Creator自身插件、Qt Quick扩展插件。 其他项目: 创建单元测试项目、子目录项…...

运用MinIO技术服务器实现文件上传——在Linux系统上安装和启动(一)

# MinIO 单机版环境搭建详解 ## 1. 简介 随着大数据时代的到来&#xff0c;数据存储的需求日益增大&#xff0c;如何有效地存储和管理大规模的非结构化数据成为许多企业和开发者面临的挑战。MinIO 作为一个高性能、分布式对象存储系统&#xff0c;致力于为用户提供简单、快速…...

Python技术深度探索:从基础到进阶的实践之旅(第一篇)

Python技术深度探索&#xff1a;从基础到进阶的实践之旅&#xff08;第一篇&#xff09; 在编程的世界里&#xff0c;Python以其简洁的语法、强大的库支持和广泛的应用领域&#xff0c;成为了无数开发者心中的“瑞士军刀”。无论是数据分析、机器学习、Web开发&#xff0c;还是…...

利士策分享,旅游是否要舟车劳顿才能尽兴?

利士策分享&#xff0c;旅游是否要舟车劳顿才能尽兴&#xff1f; 国庆假期&#xff0c;当夜幕降临&#xff0c;城市灯火阑珊&#xff0c;一场关于美食与等待的较量悄然上演。 李女士在北京天坛公园附近餐厅的等位经历——前方1053桌的壮观景象&#xff0c;不仅让人咋舌&#xf…...

C++入门——类的默认成员函数(取地址运算符重载)

文章目录 一、const成员函数二、取地址运算符重载总结 一、const成员函数 1.将const修饰的成员函数称之为const成员函数&#xff0c;const修饰成员函数放到成员函数参数列表的后⾯。2.const实际修饰该成员函数隐含的this指针&#xff0c;表明在该成员函数中不能对类的任何成员进…...

学习记录:js算法(四十九):二叉树的层序遍历

文章目录 二叉树的层序遍历网上思路队列循环 总结 二叉树的层序遍历 给你二叉树的根节点 root &#xff0c;返回其节点值的层序遍历 。 &#xff08;即逐层地&#xff0c;从左到右访问所有节点&#xff09;。 图一&#xff1a; 示例 1&#xff1a;如图一 输入&#xff1a;roo…...

【PCB工艺】表面贴装技术中常见错误

系列文章目录 1.元件基础 2.电路设计 3.PCB设计 4.元件焊接 5.板子调试 6.程序设计 7.算法学习 8.编写exe 9.检测标准 10.项目举例 11.职业规划 文章目录 1、什么是SMT和SMD2、表面贴装技术的优势是什么&#xff1f;3、通孔和表面贴装技术之间的区别是什么&#xff1f;4、焊…...

3.使用条件语句编写存储过程(3/10)

引言 在现代数据库管理系统中&#xff0c;存储过程扮演着至关重要的角色。它们是一组为了执行特定任务而编写的SQL语句&#xff0c;这些语句被保存在数据库中&#xff0c;可以被重复调用。存储过程不仅可以提高数据库操作的效率&#xff0c;还可以增强数据的安全性和一致性。此…...

Effective C++中文版学习记录(三)

Effective C中文版学习记录&#xff08;三&#xff09; 章节三&#xff1a;资源管理 进度&#xff1a;17/55 文章目录 Effective C中文版学习记录&#xff08;三&#xff09;条款13、以对象管理资源条款14、在资源管理类中小心copying行为条款15、在资源管理类中提供对原始资…...

VBA学习(76):文件合并神器/代码

1.定义变量 Dim savePath As String Dim SaveFile As String Dim dataFolder As String Dim FileSystem As Object Dim folder As Object Dim FileExtn As String Dim t As Integer Dim blnCkb As Boolean 2.自定保存文件名、选择待合并文件所在文件夹 Private Sub CkbName_…...

非农就业数据超预期,美联储降息步伐或放缓?

KlipC报道&#xff1a;当地时间10月4日&#xff0c;美国劳工部发布了最新的非农就业数据。数据显示&#xff0c;9月非农就业人数增加25.4万人&#xff0c;远超市场预期。失业率为4.1%&#xff0c;比上月略降0.1个百分点。平均时薪环比增长0.4%&#xff0c;亦高于市场预期。此外…...

每日OJ题_牛客_乒乓球筐_哈希_C++_Java

目录 牛客_乒乓球筐_哈希 题目解析 C代码 Java代码 牛客_乒乓球筐_哈希 乒乓球筐__牛客网 (nowcoder.com) 描述&#xff1a; nowcoder有两盒&#xff08;A、B&#xff09;乒乓球&#xff0c;有红双喜的、有亚力亚的……现在他需要判别A盒是否包含了B盒中所有的种类&#…...

基于ASP.NET+ SQL Server实现(Web)医院信息管理系统

医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上&#xff0c;开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识&#xff0c;在 vs 2017 平台上&#xff0c;进行 ASP.NET 应用程序和简易网站的开发&#xff1b;初步熟悉开发一…...

Module Federation 和 Native Federation 的比较

前言 Module Federation 是 Webpack 5 引入的微前端架构方案&#xff0c;允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...

零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)

本期内容并不是很难&#xff0c;相信大家会学的很愉快&#xff0c;当然对于有后端基础的朋友来说&#xff0c;本期内容更加容易了解&#xff0c;当然没有基础的也别担心&#xff0c;本期内容会详细解释有关内容 本期用到的软件&#xff1a;yakit&#xff08;因为经过之前好多期…...

重启Eureka集群中的节点,对已经注册的服务有什么影响

先看答案&#xff0c;如果正确地操作&#xff0c;重启Eureka集群中的节点&#xff0c;对已经注册的服务影响非常小&#xff0c;甚至可以做到无感知。 但如果操作不当&#xff0c;可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...

python报错No module named ‘tensorflow.keras‘

是由于不同版本的tensorflow下的keras所在的路径不同&#xff0c;结合所安装的tensorflow的目录结构修改from语句即可。 原语句&#xff1a; from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后&#xff1a; from tensorflow.python.keras.lay…...

sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!

简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求&#xff0c;并检查收到的响应。它以以下模式之一…...

解读《网络安全法》最新修订,把握网络安全新趋势

《网络安全法》自2017年施行以来&#xff0c;在维护网络空间安全方面发挥了重要作用。但随着网络环境的日益复杂&#xff0c;网络攻击、数据泄露等事件频发&#xff0c;现行法律已难以完全适应新的风险挑战。 2025年3月28日&#xff0c;国家网信办会同相关部门起草了《网络安全…...

Spring AI Chat Memory 实战指南:Local 与 JDBC 存储集成

一个面向 Java 开发者的 Sring-Ai 示例工程项目&#xff0c;该项目是一个 Spring AI 快速入门的样例工程项目&#xff0c;旨在通过一些小的案例展示 Spring AI 框架的核心功能和使用方法。 项目采用模块化设计&#xff0c;每个模块都专注于特定的功能领域&#xff0c;便于学习和…...

redis和redission的区别

Redis 和 Redisson 是两个密切相关但又本质不同的技术&#xff0c;它们扮演着完全不同的角色&#xff1a; Redis: 内存数据库/数据结构存储 本质&#xff1a; 它是一个开源的、高性能的、基于内存的 键值存储数据库。它也可以将数据持久化到磁盘。 核心功能&#xff1a; 提供丰…...

写一个shell脚本,把局域网内,把能ping通的IP和不能ping通的IP分类,并保存到两个文本文件里

写一个shell脚本&#xff0c;把局域网内&#xff0c;把能ping通的IP和不能ping通的IP分类&#xff0c;并保存到两个文本文件里 脚本1 #!/bin/bash #定义变量 ip10.1.1 #循环去ping主机的IP for ((i1;i<10;i)) doping -c1 $ip.$i &>/dev/null[ $? -eq 0 ] &&am…...