当前位置: 首页 > 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盒中所有的种类&#…...

如何保证代码质量?

一、编码阶段&#xff1a;从源头控制质量1. 统一代码规范&#xff08;强制执行&#xff09;核心目标&#xff1a;减少风格差异&#xff0c;提高可读性常见工具&#xff1a;ESLint&#xff1a;代码规范校验Prettier&#xff1a;自动格式化Stylelint&#xff1a;样式规范&#x1…...

深入解析SerialPort:从硬件流控制到实战串口通信

1. 串口通信基础&#xff1a;从水管到数据流 第一次接触串口通信时&#xff0c;我盯着电脑上的COM接口发呆了半小时。这玩意儿看起来就像老式打印机接口&#xff0c;但它却是连接硬件世界的魔法通道。串口通信就像用一根水管在两个水桶之间传递水&#xff0c;只不过我们传递的…...

ComfyUI-VideoHelperSuite:AI视频工作流的全栈解决方案

ComfyUI-VideoHelperSuite&#xff1a;AI视频工作流的全栈解决方案 【免费下载链接】ComfyUI-VideoHelperSuite Nodes related to video workflows 项目地址: https://gitcode.com/gh_mirrors/co/ComfyUI-VideoHelperSuite 1. 核心价值解析&#xff1a;图像序列到视频的…...

从YOLO到DeepLab:盘点CV任务中那些‘神级’特征融合技巧与避坑指南

从YOLO到DeepLab&#xff1a;盘点CV任务中那些‘神级’特征融合技巧与避坑指南 在计算机视觉领域&#xff0c;特征融合技术就像一位隐形的调音师&#xff0c;默默协调着神经网络中不同层次、不同来源的信息流。当你在目标检测任务中遇到小目标识别率低的问题&#xff0c;或在图…...

ESP32高精度低延迟ADC自定义库:寄存器级模拟读取优化

1. 项目概述ESP32AnalogRead Custom是由嵌入式开发者 Khrisna Ijlal Bachri 针对 ESP32 系列微控制器定制优化的模拟输入读取库。该库并非官方 ESP-IDF ADC 驱动的简单封装&#xff0c;而是聚焦于解决实际工程中高频采样、多通道同步、噪声抑制与低功耗场景下的典型痛点。其核心…...

奇偶判断算法的极端实现与优化

1. 奇偶判断算法的极端实现&#xff1a;从40亿条if语句到机器码优化1.1 项目背景与设计动机在计算机科学领域&#xff0c;判断数字奇偶性通常采用取模运算这一经典方法。然而&#xff0c;一个看似荒谬的想法引发了技术人员的深入思考&#xff1a;是否可以通过穷举所有可能的数字…...

揭秘手机摄像头隐藏功能:如何实现无网文件传输?

揭秘手机摄像头隐藏功能&#xff1a;如何实现无网文件传输&#xff1f; 【免费下载链接】cfc Demo/test android app for libcimbar. Copy files over the cell phone camera! 项目地址: https://gitcode.com/gh_mirrors/cfc/cfc 你是否曾在没有网络的情况下急需传输文件…...

OpenClaw插件开发:为Qwen3.5-4B-Claude添加Excel处理能力

OpenClaw插件开发&#xff1a;为Qwen3.5-4B-Claude添加Excel处理能力 1. 为什么需要开发Excel处理插件 上周我需要处理一批销售数据报表时&#xff0c;突然意识到一个痛点&#xff1a;虽然Qwen3.5-4B-Claude模型在结构化分析上表现优异&#xff0c;但要让它真正帮我完成Excel…...

extern ‘C‘原理与C/C++混合编程实践

1. 深入解析extern C的底层原理与工程实践1.1 C/C混合编程的核心挑战在嵌入式系统开发中&#xff0c;C与C语言的混合编程是常见需求。当C代码需要调用C语言编写的库函数时&#xff0c;编译器对函数名的处理方式差异会导致链接错误。这种差异源于两种语言对函数重载和名字空间的…...

F_Record:让绘画过程录制更高效的Photoshop开源插件

F_Record&#xff1a;让绘画过程录制更高效的Photoshop开源插件 【免费下载链接】F_Record 一款用来录制绘画过程的轻量级PS插件 项目地址: https://gitcode.com/gh_mirrors/fr/F_Record F_Record作为一款轻量级开源工具&#xff0c;是专为Photoshop用户打造的绘画过程录…...