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

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

题目思考

  1. 如何优化时间复杂度?

解决方案

思路

  • 分析题目, 最容易想到的思路是暴力两层循环, 具体做法如下:
    • 外层循环遍历每个柱子, 记录其高度 h
    • 内层向左右两边扩展, 直到超出数组范围或低于当前柱子, 记录对应的下标 l 和 r
    • 此时即为使用当前柱子高度时的矩形, 计算其面积 (r-l-1)*h 并更新最终结果
    • 这样遍历完成后就覆盖了所有可能的矩形, 其最大面积即为所求
  • 暴力算法虽然简单, 但其时间复杂度达到了 O(N^2), 根据题目输入规模, 肯定会超时, 如何优化呢?
  • 我们的目的是计算所有矩形的面积, 而高度是已知的, 如何快速得到每个柱子的左右边界呢?
  • 由于柱子的左右边界需低于当前柱子, 而且我们既需要知道高度, 又需要知道宽度(下标), 所以这里可以采用单调栈存下标的方式实现, 具体做法如下:
    • 单调栈存柱子下标, 且保证从栈顶到栈底的高度递减
    • 遍历某个柱子时, 先将其与栈顶高度比较
      • 如果栈顶更高, 则将栈顶弹出, 保证单调性, 同时栈顶对应的矩形面积也可以计算了, 其右边界就是当前柱子, 左边界就是栈顶下面一个元素或者-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&#xff08;专项突击版&#xff09;系列, 大家在公众号 算法精选 里回复 剑指offer2 就能看到该系列当前连载的所有文章了, 记得关注哦~ 题目描述 给定非负整数数组 heights &#xff0c;数组中的数字用来表示柱状…...

SpringBoot案例-部门管理-修改

目录 前言 查看页面原型&#xff0c;明确需求 页面原型 需求 阅读接口文件 思路分析 功能接口开发 控制层&#xff08;Controller类&#xff09; 业务层&#xff08;Service类&#xff09; 业务类 业务实现类 持久层&#xff08;Mapper类&#xff09; 接口测试 前…...

element-ui表格数据为空,图片占位提示

当表格的绑定数据为空时常需要显示暂无数据等字样&#xff0c;这时候就用到了empty-text <el-table:data"tableData"stripeborderempty-text"暂无数据"> 但&#xff0c;当数据为空&#xff0c;想用图片展示呢&#xff0c;如下图 方法一&#xff1a…...

C++ STL vector 模拟实现

✅<1>主页&#xff1a;我的代码爱吃辣 &#x1f4c3;<2>知识讲解&#xff1a;C之STL &#x1f525;<3>创作者&#xff1a;我的代码爱吃辣 ☂️<4>开发环境&#xff1a;Visual Studio 2022 &#x1f4ac;<5>前言&#xff1a;上次我们已经数字会用…...

51单片机学习--红外遥控(外部中断)

需要利用下面这个红外接收头&#xff0c;OUT口会发出红外信号对应的高低电平&#xff0c;由于发送的速度很快&#xff0c;所以需要把OUT引脚接在外部中断引脚上&#xff0c;当OUT一旦产生下降沿&#xff0c;马上进中断&#xff0c;这样响应会更及时。 外部中断引脚位于P3_2和P…...

后端开发10.规格模块

概述 简介 效果图...

腾讯出了一个新聊天软件M8

众所周知&#xff0c;如今国内互联网&#xff0c;微信和QQ无疑是社交领域的霸主。 下载:https://www.123pan.com/s/BP5A-RW4xh.html 不过&#xff0c;它们也有各自局限性&#xff0c;比如难以结识新朋友、功能过于复杂等。 这让用户产生厌倦&#xff0c;再加上近几年AI、元宇…...

C++ QT(一)

目录 初识QtQt 是什么Qt 能做什么Qt/C与QML 如何选择Qt 版本Windows 下安装QtLinux 下安装Qt安装Qt配置Qt Creator 输入中文配置Ubuntu 中文环境配置中文输入法 Qt Creator 简单使用Qt Creator 界面组成Qt Creator 设置 第一个Qt 程序新建一个项目项目文件介绍项目文件*.pro样式…...

微信小程序时钟

微信小程序自定义时钟&#xff0c;模拟翻牌时钟。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设置代理&#xff1a; httprunner 库本身没有提供设置代理的接口&#xff0c;但是底层使用了urllib.requests 等库&#xff0c;可以设置HTTP_PROXY 和HTTPS_PROXY 环境变量&#xff0c;常用的网络库会自动识别这些环境变量。 日常调试使用代理&#xff08;如charles…...

opsForHash() 与 opsForValue 请问有什么区别?

&#x1f449;&#xff1a;&#x1f517;官方API参考手册 如图&#xff0c;opsForHash()返回HashOperations<K,HK,HV>但是 opsForValue()返回ValueOperations<K,V>… 区别就是opsForHash的返回值泛型中有K,HK,HV,其中K是Redis指定的某个数据库里面某一个关键字(由…...

具有吸引子的非线性系统(MatlabSimulink实现)

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

Linux一些常见的命令

1. 基础命令 1. ls&#xff1a; 列出目录内容。- 例如&#xff1a;ls -l 以长格式列出文件和目录。2. cd&#xff1a; 切换工作目录。- 例如&#xff1a;cd /home/user 进入 /home/user 目录。3. pwd&#xff1a; 显示当前工作目录的路径。4. mkdir&#xff1a; 创建新目录。-…...

正则表达式的基本知识

正则表达式是一种用于匹配和操作字符串的强大工具。它是由一系列字符和特殊符号组成的模式&#xff0c;可以用来检查字符串是否符合某种模式&#xff0c;进行匹配、替换、提取等操作。 下面是一些常见的正则表达式元字符和语法&#xff1a; 1. 字符匹配&#xff1a; - 普通…...

如何⽤webpack 来优化前端性能

如何⽤webpack 来优化前端性能&#xff1f; ⽤webpack 优化前端性能是指优化 webpack 的输出结果&#xff0c;让打包的最终结果在浏览器运⾏快速⾼效。 压缩代码&#xff1a;删除多余的代码、注释、简化代码的写法等等⽅式。可以利⽤webpack的 UglifyJsPlugin 和 ParallelUgl…...

人机交互中的混合多重反馈

人机交互中态、势、感、知的混合多重反馈是指在交互过程中综合运用不同方面的反馈信息&#xff0c;包括用户态度&#xff08;态&#xff09;、行为动势&#xff08;势&#xff09;、情感体验&#xff08;感&#xff09;和认知反馈&#xff08;知&#xff09;。这种多重反馈可以…...

CSS:服务器字体 与 响应式布局(用法 + 例子 + 效果)

文章目录 服务器字体定义 服务器字体使用例子 响应式布局设备类型设备特性例子 服务器字体 解决字体不一致而产生的。 首先&#xff0c;在网上把字体下载好。 定义 服务器字体 font-face{font-family:字体名称;src:url(字体资源路径); }使用 在需要使用的选择器里加上 font…...

24届近3年上海电力大学自动化考研院校分析

今天给大家带来的是上海电力大学控制考研分析 满满干货&#xff5e;还不快快点赞收藏 一、上海电力大学 学校简介 上海电力大学&#xff08;Shanghai University of Electric Power&#xff09;&#xff0c;位于上海市&#xff0c;是中央与上海市共建、以上海市管理为主的全日…...

PostgreSQL查询慢sql原因和优化方案

PostgreSQL sql查询慢优化方案有一下几种解决方案&#xff1a; 1.关闭会话 查询慢sql的执行会话&#xff0c;关闭进程。 查看数据库后台连接进程 SELECT count(*) FROM pg_stat_activity;SELECT * FROM pg_stat_activity; 查看数据库后台连接进程&#xff0c;但是此条SQL不…...

Leetcode 21. 合并两个有序链表

题目描述 题目链接&#xff1a;https://leetcode.cn/problems/merge-two-sorted-lists/description/ 思路 两个链表都是升序链表&#xff0c;新建一个链表&#xff0c;引入伪头节点作为辅助节点&#xff0c;将各节点添加到伪节点之后&#xff0c;再用一个cur节点指向新链表的…...

关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案

问题描述&#xff1a;iview使用table 中type: "index",分页之后 &#xff0c;索引还是从1开始&#xff0c;试过绑定后台返回数据的id, 这种方法可行&#xff0c;就是后台返回数据的每个页面id都不完全是按照从1开始的升序&#xff0c;因此百度了下&#xff0c;找到了…...

【磁盘】每天掌握一个Linux命令 - iostat

目录 【磁盘】每天掌握一个Linux命令 - iostat工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景 注意事项 【磁盘】每天掌握一个Linux命令 - iostat 工具概述 iostat&#xff08;I/O Statistics&#xff09;是Linux系统下用于监视系统输入输出设备和CPU使…...

MySQL用户和授权

开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务&#xff1a; test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...

大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计

随着大语言模型&#xff08;LLM&#xff09;参数规模的增长&#xff0c;推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长&#xff0c;而KV缓存的内存消耗可能高达数十GB&#xff08;例如Llama2-7B处理100K token时需50GB内存&a…...

短视频矩阵系统文案创作功能开发实践,定制化开发

在短视频行业迅猛发展的当下&#xff0c;企业和个人创作者为了扩大影响力、提升传播效果&#xff0c;纷纷采用短视频矩阵运营策略&#xff0c;同时管理多个平台、多个账号的内容发布。然而&#xff0c;频繁的文案创作需求让运营者疲于应对&#xff0c;如何高效产出高质量文案成…...

嵌入式学习笔记DAY33(网络编程——TCP)

一、网络架构 C/S &#xff08;client/server 客户端/服务器&#xff09;&#xff1a;由客户端和服务器端两个部分组成。客户端通常是用户使用的应用程序&#xff0c;负责提供用户界面和交互逻辑 &#xff0c;接收用户输入&#xff0c;向服务器发送请求&#xff0c;并展示服务…...

AGain DB和倍数增益的关系

我在设置一款索尼CMOS芯片时&#xff0c;Again增益0db变化为6DB&#xff0c;画面的变化只有2倍DN的增益&#xff0c;比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析&#xff1a; 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...

无人机侦测与反制技术的进展与应用

国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机&#xff08;无人驾驶飞行器&#xff0c;UAV&#xff09;技术的快速发展&#xff0c;其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统&#xff0c;无人机的“黑飞”&…...

DingDing机器人群消息推送

文章目录 1 新建机器人2 API文档说明3 代码编写 1 新建机器人 点击群设置 下滑到群管理的机器人&#xff0c;点击进入 添加机器人 选择自定义Webhook服务 点击添加 设置安全设置&#xff0c;详见说明文档 成功后&#xff0c;记录Webhook 2 API文档说明 点击设置说明 查看自…...

Qt 事件处理中 return 的深入解析

Qt 事件处理中 return 的深入解析 在 Qt 事件处理中&#xff0c;return 语句的使用是另一个关键概念&#xff0c;它与 event->accept()/event->ignore() 密切相关但作用不同。让我们详细分析一下它们之间的关系和工作原理。 核心区别&#xff1a;不同层级的事件处理 方…...