Leetcode 剑指 Offer II 039. 直方图最大矩形面积
题目难度: 困难
原题链接
今天继续更新 Leetcode 的剑指 Offer(专项突击版)系列, 大家在公众号 算法精选 里回复
剑指offer2就能看到该系列当前连载的所有文章了, 记得关注哦~
题目描述
给定非负整数数组 heights ,数组中的数字用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。
求在该柱状图中,能够勾勒出来的矩形的最大面积。
示例 1:

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

- 输入: heights = [2,4]
- 输出: 4
提示:
- 1 <= heights.length <=10^5
- 0 <= heights[i] <= 10^4
题目思考
- 如何优化时间复杂度?
解决方案
思路
- 分析题目, 最容易想到的思路是暴力两层循环, 具体做法如下:
- 外层循环遍历每个柱子, 记录其高度 h
- 内层向左右两边扩展, 直到超出数组范围或低于当前柱子, 记录对应的下标 l 和 r
- 此时即为使用当前柱子高度时的矩形, 计算其面积 (r-l-1)*h 并更新最终结果
- 这样遍历完成后就覆盖了所有可能的矩形, 其最大面积即为所求
- 暴力算法虽然简单, 但其时间复杂度达到了 O(N^2), 根据题目输入规模, 肯定会超时, 如何优化呢?
- 我们的目的是计算所有矩形的面积, 而高度是已知的, 如何快速得到每个柱子的左右边界呢?
- 由于柱子的左右边界需低于当前柱子, 而且我们既需要知道高度, 又需要知道宽度(下标), 所以这里可以采用单调栈存下标的方式实现, 具体做法如下:
- 单调栈存柱子下标, 且保证从栈顶到栈底的高度递减
- 遍历某个柱子时, 先将其与栈顶高度比较
- 如果栈顶更高, 则将栈顶弹出, 保证单调性, 同时栈顶对应的矩形面积也可以计算了, 其右边界就是当前柱子, 左边界就是栈顶下面一个元素或者-1(对应栈顶左边没有更低柱子的情况),
右-左-1就是矩形的宽 - 否则就退出循环, 将当前柱子压入栈中, 此时栈顶到栈底的高度仍是递减的
- 如果栈顶更高, 则将栈顶弹出, 保证单调性, 同时栈顶对应的矩形面积也可以计算了, 其右边界就是当前柱子, 左边界就是栈顶下面一个元素或者-1(对应栈顶左边没有更低柱子的情况),
- 遍历完所有柱子后, 栈中仍可能存在一些柱子, 此时说明这些柱子右边没有更高的柱子, 其右边界就是数组长度, 左边界和上面情况一样, 依次将其弹出并计算面积
- 最终结果就是上述所有矩形面积的最小值
- 利用单调栈, 我们使用和暴力算法一样的思路计算所有矩形面积, 但却将时间复杂度成功降低到了 O(N), 因为每个柱子只需要处理两次(一次入栈一次出栈)
- 下面的代码就对应了上面的整个过程, 并且有详细的注释, 方便大家理解
复杂度
- 时间复杂度 O(N): 数组每个元素最多处理 2 遍 (压入和弹出栈)
- 空间复杂度 O(N): 栈最多存 N 个元素
代码
class Solution:def largestRectangleArea(self, heights: List[int]) -> int:# stack存储柱子的下标, 且其高度满足从栈顶到栈底递减stack = []res = 0for r, h in enumerate(heights):while stack and heights[stack[-1]] > h:# 栈顶高度大于当前高度, 可以计算栈顶柱子对应的矩形面积了# 栈顶柱子的右边界r就是当前下标, 左边界l是上一个栈顶或-1(上一个栈顶不存在时)ch = heights[stack.pop()]l = -1 if not stack else stack[-1]# 宽*高res = max(res, (r - l - 1) * ch)stack.append(r)# 如果遍历结束后栈中仍有元素, 则说明这些柱子右边没有比它更低的柱子了, 需要计算它们对应的矩形面积while stack:ch = heights[stack.pop()]# 栈顶柱子的右边界r就是数组长度, 左边界l是上一个栈顶或-1(上一个栈顶不存在时)r = len(heights)l = -1 if not stack else stack[-1]# 宽*高res = max(res, (r - l - 1) * ch)return res
大家可以在下面这些地方找到我~😊
我的 GitHub
我的 Leetcode
我的 CSDN
我的知乎专栏
我的头条号
我的牛客网博客
我的公众号: 算法精选, 欢迎大家扫码关注~😊

相关文章:
Leetcode 剑指 Offer II 039. 直方图最大矩形面积
题目难度: 困难 原题链接 今天继续更新 Leetcode 的剑指 Offer(专项突击版)系列, 大家在公众号 算法精选 里回复 剑指offer2 就能看到该系列当前连载的所有文章了, 记得关注哦~ 题目描述 给定非负整数数组 heights ,数组中的数字用来表示柱状…...
SpringBoot案例-部门管理-修改
目录 前言 查看页面原型,明确需求 页面原型 需求 阅读接口文件 思路分析 功能接口开发 控制层(Controller类) 业务层(Service类) 业务类 业务实现类 持久层(Mapper类) 接口测试 前…...
element-ui表格数据为空,图片占位提示
当表格的绑定数据为空时常需要显示暂无数据等字样,这时候就用到了empty-text <el-table:data"tableData"stripeborderempty-text"暂无数据"> 但,当数据为空,想用图片展示呢,如下图 方法一:…...
C++ STL vector 模拟实现
✅<1>主页:我的代码爱吃辣 📃<2>知识讲解:C之STL 🔥<3>创作者:我的代码爱吃辣 ☂️<4>开发环境:Visual Studio 2022 💬<5>前言:上次我们已经数字会用…...
51单片机学习--红外遥控(外部中断)
需要利用下面这个红外接收头,OUT口会发出红外信号对应的高低电平,由于发送的速度很快,所以需要把OUT引脚接在外部中断引脚上,当OUT一旦产生下降沿,马上进中断,这样响应会更及时。 外部中断引脚位于P3_2和P…...
后端开发10.规格模块
概述 简介 效果图...
腾讯出了一个新聊天软件M8
众所周知,如今国内互联网,微信和QQ无疑是社交领域的霸主。 下载:https://www.123pan.com/s/BP5A-RW4xh.html 不过,它们也有各自局限性,比如难以结识新朋友、功能过于复杂等。 这让用户产生厌倦,再加上近几年AI、元宇…...
C++ QT(一)
目录 初识QtQt 是什么Qt 能做什么Qt/C与QML 如何选择Qt 版本Windows 下安装QtLinux 下安装Qt安装Qt配置Qt Creator 输入中文配置Ubuntu 中文环境配置中文输入法 Qt Creator 简单使用Qt Creator 界面组成Qt Creator 设置 第一个Qt 程序新建一个项目项目文件介绍项目文件*.pro样式…...
微信小程序时钟
微信小程序自定义时钟,模拟翻牌时钟。1、页面布局 <view class"date-time-box"><view class"date-box">{{nowDate}}</view><view class"time-box"><view><image class"pic01 {{move[0]?move…...
HttpRunner自动化工具之设置代理和请求证书验证
httprunner设置代理: httprunner 库本身没有提供设置代理的接口,但是底层使用了urllib.requests 等库,可以设置HTTP_PROXY 和HTTPS_PROXY 环境变量,常用的网络库会自动识别这些环境变量。 日常调试使用代理(如charles…...
opsForHash() 与 opsForValue 请问有什么区别?
👉:🔗官方API参考手册 如图,opsForHash()返回HashOperations<K,HK,HV>但是 opsForValue()返回ValueOperations<K,V>… 区别就是opsForHash的返回值泛型中有K,HK,HV,其中K是Redis指定的某个数据库里面某一个关键字(由…...
具有吸引子的非线性系统(MatlabSimulink实现)
💥💥💞💞欢迎来到本博客❤️❤️💥💥 🏆博主优势:🌞🌞🌞博客内容尽量做到思维缜密,逻辑清晰,为了方便读者。 ⛳️座右铭&a…...
Linux一些常见的命令
1. 基础命令 1. ls: 列出目录内容。- 例如:ls -l 以长格式列出文件和目录。2. cd: 切换工作目录。- 例如:cd /home/user 进入 /home/user 目录。3. pwd: 显示当前工作目录的路径。4. mkdir: 创建新目录。-…...
正则表达式的基本知识
正则表达式是一种用于匹配和操作字符串的强大工具。它是由一系列字符和特殊符号组成的模式,可以用来检查字符串是否符合某种模式,进行匹配、替换、提取等操作。 下面是一些常见的正则表达式元字符和语法: 1. 字符匹配: - 普通…...
如何⽤webpack 来优化前端性能
如何⽤webpack 来优化前端性能? ⽤webpack 优化前端性能是指优化 webpack 的输出结果,让打包的最终结果在浏览器运⾏快速⾼效。 压缩代码:删除多余的代码、注释、简化代码的写法等等⽅式。可以利⽤webpack的 UglifyJsPlugin 和 ParallelUgl…...
人机交互中的混合多重反馈
人机交互中态、势、感、知的混合多重反馈是指在交互过程中综合运用不同方面的反馈信息,包括用户态度(态)、行为动势(势)、情感体验(感)和认知反馈(知)。这种多重反馈可以…...
CSS:服务器字体 与 响应式布局(用法 + 例子 + 效果)
文章目录 服务器字体定义 服务器字体使用例子 响应式布局设备类型设备特性例子 服务器字体 解决字体不一致而产生的。 首先,在网上把字体下载好。 定义 服务器字体 font-face{font-family:字体名称;src:url(字体资源路径); }使用 在需要使用的选择器里加上 font…...
24届近3年上海电力大学自动化考研院校分析
今天给大家带来的是上海电力大学控制考研分析 满满干货~还不快快点赞收藏 一、上海电力大学 学校简介 上海电力大学(Shanghai University of Electric Power),位于上海市,是中央与上海市共建、以上海市管理为主的全日…...
PostgreSQL查询慢sql原因和优化方案
PostgreSQL sql查询慢优化方案有一下几种解决方案: 1.关闭会话 查询慢sql的执行会话,关闭进程。 查看数据库后台连接进程 SELECT count(*) FROM pg_stat_activity;SELECT * FROM pg_stat_activity; 查看数据库后台连接进程,但是此条SQL不…...
Leetcode 21. 合并两个有序链表
题目描述 题目链接:https://leetcode.cn/problems/merge-two-sorted-lists/description/ 思路 两个链表都是升序链表,新建一个链表,引入伪头节点作为辅助节点,将各节点添加到伪节点之后,再用一个cur节点指向新链表的…...
React hook之useRef
React useRef 详解 useRef 是 React 提供的一个 Hook,用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途,下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...
基于ASP.NET+ SQL Server实现(Web)医院信息管理系统
医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上,开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识,在 vs 2017 平台上,进行 ASP.NET 应用程序和简易网站的开发;初步熟悉开发一…...
前端倒计时误差!
提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...
循环冗余码校验CRC码 算法步骤+详细实例计算
通信过程:(白话解释) 我们将原始待发送的消息称为 M M M,依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)(意思就是 G ( x ) G(x) G(x) 是已知的)࿰…...
蓝桥杯 2024 15届国赛 A组 儿童节快乐
P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡,轻快的音乐在耳边持续回荡,小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下,六一来了。 今天是六一儿童节,小蓝老师为了让大家在节…...
大语言模型如何处理长文本?常用文本分割技术详解
为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...
c++ 面试题(1)-----深度优先搜索(DFS)实现
操作系统:ubuntu22.04 IDE:Visual Studio Code 编程语言:C11 题目描述 地上有一个 m 行 n 列的方格,从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子,但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...
【项目实战】通过多模态+LangGraph实现PPT生成助手
PPT自动生成系统 基于LangGraph的PPT自动生成系统,可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析:自动解析Markdown文档结构PPT模板分析:分析PPT模板的布局和风格智能布局决策:匹配内容与合适的PPT布局自动…...
MODBUS TCP转CANopen 技术赋能高效协同作业
在现代工业自动化领域,MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步,这两种通讯协议也正在被逐步融合,形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...
第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明
AI 领域的快速发展正在催生一个新时代,智能代理(agents)不再是孤立的个体,而是能够像一个数字团队一样协作。然而,当前 AI 生态系统的碎片化阻碍了这一愿景的实现,导致了“AI 巴别塔问题”——不同代理之间…...
