代码随想录算法训练营Day 60 || 84.柱状图中最大的矩形

84.柱状图中最大的矩形

力扣题目链接(opens new window)

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

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

  • 1 <= heights.length <=10^5
  • 0 <= heights[i] <= 10^4

  1. 初始化栈和最大面积变量:

    • 创建一个空栈 stack 来存储柱子的索引。
    • 初始化一个变量 max_area 用于存储遍历过程中计算出的最大面积。
  2. 处理每个柱子:

    • 遍历每个柱子的高度 heights,同时在 heights 的末尾添加一个高度为 0 的柱子,以确保栈中的所有柱子都能被处理。
    • 对于每个柱子 i
      • 当栈不为空且当前柱子的高度 heights[i] 小于栈顶柱子的高度时,执行以下操作:
        • 弹出栈顶元素,该元素索引记为 top。这意味着以 heights[top] 为高的矩形的右边界已经确定。
        • 计算矩形的宽度:
          • 如果栈为空,宽度即为当前柱子的索引 i(因为左边界是起始位置)。
          • 如果栈不为空,宽度为 i - stack[-1] - 1(当前索引减去新的栈顶元素索引,减去1表示两个柱子间的距离)。
        • 计算矩形面积:heights[top] * 宽度,并更新 max_area
      • 将当前柱子索引 i 压入栈中。
  3. 返回最大面积:

    • 经过上述遍历,我们已经计算出了每个可能的矩形的面积,并记录了其中的最大值。
    • 返回 max_area 作为结果。

 

class Solution:
    def largestRectangleArea(self, heights):
        stack = []
        max_area = 0
        heights.append(0)  # 添加一个高度为0的柱子,确保所有柱子都被弹出

        for i, h in enumerate(heights):
            while stack and heights[stack[-1]] > h:
                height = heights[stack.pop()]
                width = i if not stack else i - stack[-1] - 1
                max_area = max(max_area, height * width)
            stack.append(i)

        return max_area


# solution = Solution()
# example_heights = [2, 1, 5, 6, 2, 3]
# result = solution.largestRectangleArea(example_heights)
# print(result)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/180317.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

安卓毕业设计基于安卓android微信小程序的家校通系统

运行环境 开发语言&#xff1a;Java 框架&#xff1a;ssm JDK版本&#xff1a;JDK1.8 服务器&#xff1a;tomcat7 小程序框架&#xff1a;uniapp 小程序开发软件&#xff1a;HBuilder X 小程序运行软件&#xff1a;微信开发者 项目介绍 基于微信小程序的家校通系统的设计基…

ECRS生产工时分析软件:工业效率提升的隐形引擎

降本增效往往是企业开工规划的第一步。那到底降什么本&#xff0c;增什么效呢&#xff0c;对于很多企业来说&#xff0c;都是从采购成本入手&#xff0c;结果采购成本是降下来了&#xff0c;但是整体品质却下降了。实际上&#xff0c;要降本增效&#xff0c;优化现场管理才是企…

DBS note4:Buffer Management

目录 1、介绍 2、缓冲池 3、处理页面请求 4、LRU替换和时钟策略 1&#xff09;顺序扫描性能 - LRU 5、最近最常使用替换策略&#xff08;MRU Replacement&#xff09; 1&#xff09;Sequential Scanning Performance - MRU 6、练习题 1&#xff09;判断真假 2&#xf…

python实战—核心基础3(RGB模式颜色转换器) lv1

目录 一、核心代码解释 二、代码 三、运行截图 一、核心代码解释 1、hex() 函数 参数说明&#xff1a; x -- 10进制整数 返回值&#xff1a; 返回16进制数&#xff0c;以字符串形式表示。 实例&#xff1a; 以下实例展示了 hex 的使用方法&#xff1a; >>>h…

单片机调试技巧--修改bin文件实现断点

fromelf --text -a -c --outputall.dis F103_Moduel\F103_Moduel.axffromelf --bin --outputtest.bin F103_Moduel\F103_Moduel.axf 在启动文件中&#xff0c;修改UsageFault_Handler UsageFault_Handler\PROC; get current contextTST lr, #0x04 ; if(!EXC_RETURN[2])ITE…

WifiManager的getConnectionInfo被弃用了?快来使用ConnectivityManager获取更全的网络信息吧

前言 最近在使用flutter写桌面端的一个adb工具&#xff0c;可以使用adb命令无线连接设备&#xff0c;需要电脑和手机在同一局域网内&#xff0c;但是需要手机的ip地址。于是我想到写一个android桌面小组件&#xff0c;点一下就获取WiFi的ipv4地址并显示出来&#xff0c;先去找…

计算机网络之运输层

一、概述 物理层、数据链路层以及网络层它们共同解决了将主机通过异构网络互联起来所面临的的问题&#xff0c;实现了主机到主机的通信 但实际上在计算机网络中进行通信的真正实体是位于通信两端主机中的进程 如何为运行在不同主机上的应用进程提供直接的通信服务时运输层的任务…

【深度学习】Transformer简介

近年来&#xff0c;Transformer模型在自然语言处理&#xff08;NLP&#xff09;领域中横扫千军&#xff0c;以BERT、GPT为代表的模型屡屡屠榜&#xff0c;目前已经成为了该领域的标准模型。同时&#xff0c;在计算机视觉等领域中&#xff0c;Transformer模型也逐渐得到了重视&a…

第十一章 docker swarm集群部署

文章目录 前言一、安装docker1.1 解压1.2 配置docker 存储目录和dns1.3 添加docker.service文件1.4 docker 启动验证 二、docker swarm 集群配置2.1 关闭selinux2.2 设置主机名称并加入/etc/hosts2.3 修改各个服务器名称&#xff08;uname -a 进行验证&#xff09;2.4 初始化sw…

【SpringBoot篇】Spring_Task定时任务框架

文章目录 &#x1f339;概述&#x1f33a;应用场景&#x1f384;cron表达式&#x1f6f8;入门案例&#x1f38d;实际应用 &#x1f339;概述 Spring Task 是 Spring 框架提供的一种任务调度和异步处理的解决方案。可以按照约定的时间自动执行某个代码逻辑它可以帮助开发者在 S…

PTA 六度空间

“六度空间”理论又称作“六度分隔&#xff08;Six Degrees of Separation&#xff09;”理论。这个理论可以通俗地阐述为&#xff1a;“你和任何一个陌生人之间所间隔的人不会超过六个&#xff0c;也就是说&#xff0c;最多通过五个人你就能够认识任何一个陌生人。”如图1所示…

Springboot+vue的新冠病毒密接者跟踪系统(有报告)。Javaee项目,springboot vue前后端分离项目

演示视频&#xff1a; Springbootvue的新冠病毒密接者跟踪系统(有报告)。Javaee项目&#xff0c;springboot vue前后端分离项目 项目介绍&#xff1a; 本文设计了一个基于Springbootvue的新冠病毒密接者跟踪系统&#xff0c;采用M&#xff08;model&#xff09;V&#xff08;v…

【实用】PPT没几页内存很大怎么解决

PPT页数很少但导出内存很大解决方法 1.打开ppt点击左上角 “文件”—“选项” 2.对话框选择 “常规与保存” &#xff08;1&#xff09;如果想要文件特别小时可 取消勾选 “将字体嵌入文件” &#xff08;2&#xff09;文件大小适中 可选择第一个选项 “仅最入文档中所用的字…

【数组栈】实现

目录 栈的概念及其结构 栈的实现 数组栈 链式栈 栈的常见接口实现 主函数Test.c 头文件&函数声明Stack.h 头文件 函数声明 函数实现Stack.c 初始化SLInit 扩容Createcapacity 压栈STPush 出栈STPop 栈顶元素STTop 判断栈是否为空STempty 栈内元素个数STSzi…

ABB机 器 人 操 作 培 训

目 录 1 培训手册介绍 ---------------------------------------------2 2 系统安全与环境保护 ---------------------------------------------3 3 机器人综述 ---------------------------------------------5 4 机器人示教 --------------------------------------------12…

普通平衡树

题意&#xff1a;略&#xff0c;题中较清晰。 用二叉查找树来存储数据&#xff0c;为了增加效率&#xff0c;尽量使左子树和右子树的深度差不超过一&#xff0c;这样可以时间控制在logn&#xff0c;效率比较高。 右旋和左旋&#xff0c;目的是为了维护二叉树的操作&#xff0…

CSGO搬砖项目全面讲解 ,CSGO搬砖注意事项

Steam/CSGO游戏搬砖全套操作流程之如何选品&#xff08;第二课&#xff09; 一个游戏只要能搬&#xff0c;只要体量不够大&#xff0c;很快就会货币价格暴跌&#xff0c;直接凉凉。市面上的能稳定手动搬砖的游戏越来越少。所以对于兼职赚点外快的散人搬砖党来说&#xff0c;找一…

【Vue入门篇】基础篇—Vue指令,Vue生命周期

&#x1f38a;专栏【JavaSE】 &#x1f354;喜欢的诗句&#xff1a;更喜岷山千里雪 三军过后尽开颜。 &#x1f386;音乐分享【如愿】 &#x1f384;欢迎并且感谢大家指出小吉的问题&#x1f970; 文章目录 &#x1f354;Vue概述&#x1f384;快速入门&#x1f33a;Vue指令⭐v-…

微信小程序登录获取不到头像和昵称解决办法

微信小程序登录获取不到头像和昵称主要原因是&#xff1a;小程序wx.getUserProfile接口被收回&#xff01; 大家可以按照文档操作↓ PS&#xff1a; 针对小程序wx.getUserProfile接口将被收回后做出的授权调整 小程序文档中提出的调整说明 对于此次变化&#xff0c;现将小程…

如何满足BMW EDI项目的PKT需求?

近期宝马BMW&#xff08;以下简称BMW&#xff09;在其部分供应商之间试点推进PKT项目&#xff0c;BMW为什么要启动 PKT 计划呢&#xff1f; 业务系统全面升级统一全球所有宝马工厂的流程 宝马内部的物流供货流程 近期BMW PKT需求主要针对其内部物流供货流程展开&#xff1a; …