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

LeetCode--84. 柱状图中最大的矩形【单调栈】

84. 柱状图中最大的矩形


正文

题目如下

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

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

这道题暴力很简单,但是时间复杂度是O(N^2),在这里我们不予考虑,我在这里主要介绍一下单调栈的做法。

单调栈主要的思路就是,将遍历到的元素下标压入栈中,如果当前遍历的元素小于栈顶元素,就没有遵循单调的原则,需要先把栈中大于当前遍历到的数字的元素弹出,再把当前遍历的元素压入栈中,在这个过程中,我们还需要重新计算最大的矩形面积。

如何计算?

  • 首先我们需要明确,我们的栈是存储的下标,通过下标的差值我们可以计算出宽度,而且栈中元素是保持着单调递增的趋势,所以我们每次弹出的下标对应的数值都可以作为我们的矩形的高,这样便可以计算出我们的矩形面积。

为什么这样做能得出正确答案?

  • 首先,我们需要先了解一下暴力的做法,暴力是通过两个for循环遍历来实现的矩形的面积最大值计算,而单调栈是只在每次弹出元素的时候重新计算矩形面积,每个元素最多入栈,出栈一次,所以时间复杂度远小于暴力做法。
  • 但我们仔细想一下就能够知道,暴力做法是有很多多余的计算步骤的,比如以[1,2,3,4,5,6,1]为例子,遍历1的时候,会把2,3,4,5,6,1遍历完,显然效率很低,而单调栈在弹出元素时,能够确定,以当前下标对应的矩形的高的最大面积是多少,想清楚这一点,这道题就迎刃而解了。

下面是代码

func largestRectangleArea(heights []int) int {var st []intans := 0heights = append(heights, -1)for i := 0; i < len(heights); i ++ {for len(st) != 0 && heights[i] < heights[st[len(st) - 1]] {idx := st[len(st) - 1]st = st[:len(st) - 1]var l intif len(st) == 0 {l = -1} else {l = st[len(st) - 1]}ans = Max(ans, (i - l - 1) * heights[idx])}st = append(st, i)}return ans}func Max(a int, b int) int {if a >= b {return a}return b}

结语

这道题思路来源于bilibili,如果觉得不清晰可以看看这个视频。

相关文章:

LeetCode--84. 柱状图中最大的矩形【单调栈】

84. 柱状图中最大的矩形 正文 题目如下 给定 n 个非负整数&#xff0c;用来表示柱状图中各个柱子的高度。每个柱子彼此相邻&#xff0c;且宽度为 1 。 求在该柱状图中&#xff0c;能够勾勒出来的矩形的最大面积。 这道题暴力很简单&#xff0c;但是时间复杂度是O(N^2)&#xf…...

网络工程师 (8)存储管理

一、页式存储基本原理 &#xff08;一&#xff09;内存划分 页式存储首先将内存物理空间划分成大小相等的存储块&#xff0c;这些块通常被称为“页帧”或“物理页”。每个页帧的大小是固定的&#xff0c;例如常见的页帧大小有4KB、8KB等&#xff0c;这个大小由操作系统决定。同…...

【Leetcode 每日一题】541. 反转字符串 II

问题背景 给定一个字符串 s s s 和一个整数 k k k&#xff0c;从字符串开头算起&#xff0c;每计数至 2 k 2k 2k 个字符&#xff0c;就反转这 2 k 2k 2k 字符中的前 k k k 个字符。 如果剩余字符少于 k k k 个&#xff0c;则将剩余字符全部反转。如果剩余字符小于 2 k…...

MSA Transformer

过去的蛋白质语言模型以单个序列为输入&#xff0c;MSA Transformer以多序列比对的形式将一组序列作为输入。该模型将行和列注意力交织在输入序列中&#xff0c;并在许多蛋白质家族中使用mask语言建模目标进行训练。模型的性能远超过了当时最先进的无监督学习方法&#xff0c;其…...

Vue.js组件开发-实现全屏焦点图片带图标导航按钮控制图片滑动切换

使用 Vue 实现全屏焦点图片带图标导航按钮控制图片滑动切换 步骤 创建 Vue 项目&#xff1a;可以使用 Vue CLI 快速创建一个新的 Vue 项目。设计组件结构&#xff1a;创建一个包含图片展示区域和导航按钮的组件。实现图片滑动切换逻辑&#xff1a;通过点击导航按钮切换图片。…...

Linux系统上安装与配置 MySQL( CentOS 7 )

目录 1. 下载并安装 MySQL 官方 Yum Repository 2. 启动 MySQL 并查看运行状态 3. 找到 root 用户的初始密码 4. 修改 root 用户密码 5. 设置允许远程登录 6. 在云服务器配置 MySQL 端口 7. 关闭防火墙 8. 解决密码错误的问题 前言 在 Linux 服务器上安装并配置 MySQL …...

Vue 3 30天精进之旅:Day 10 - Vue Router

在现代单页面应用&#xff08;SPA&#xff09;中&#xff0c;路由管理是必不可少的一部分。Vue Router是Vue.js官方的路由管理库&#xff0c;它使得在Vue应用中实现路由变得简单而灵活。今天的学习将围绕以下几个方面展开&#xff1a; Vue Router概述安装和基本配置定义路由路…...

人工智能如何驱动SEO关键词优化策略的转型与效果提升

内容概要 随着数字化时代的到来&#xff0c;人工智能&#xff08;AI&#xff09;技术对各行各业的影响日益显著&#xff0c;在搜索引擎优化&#xff08;SEO&#xff09;领域尤为如此。AI的应用不仅改变了关键词研究的方法&#xff0c;而且提升了内容生成和搜索优化的效率&…...

keil5如何添加.h 和.c文件,以及如何添加文件夹

1.简介 在hal库的编程中我们一般会生成如下的几个文件夹&#xff0c;在这几个文件夹内存储着各种外设所需要的函数接口.h文件&#xff0c;和实现函数具体功能的.c文件&#xff0c;但是有时我们想要创建自己的文件夹并在这些文件夹下面创造.h .c文件来实现某些功能&#xff0c;…...

BMC PSL function(22)-printf()

printf() 含义:Print text formatted to the C library printf() routine specification Format printf(format,[arg1,......,argn]) Parameter ParameterDefinitionformattext, variable names, and control characters that specify the content and format of output t…...

【数据结构】_复杂度

目录 1. 算法效率 2. 时间复杂度 2.1 时间复杂度概念 2.2 准确的时间复杂度函数式 2.3 大O渐进表示法 2.4 时间复杂度的常见量级 2.5 时间复杂度示例 3. 空间复杂度 3.1 空间复杂度概念 3.2 空间复杂度示例 1. 算法效率 一般情况下&#xff0c;衡量一个算法的好坏是…...

pytorch实现循环神经网络

人工智能例子汇总&#xff1a;AI常见的算法和例子-CSDN博客 PyTorch 提供三种主要的 RNN 变体&#xff1a; nn.RNN&#xff1a;最基本的循环神经网络&#xff0c;适用于短时依赖任务。nn.LSTM&#xff1a;长短时记忆网络&#xff0c;适用于长序列数据&#xff0c;能有效解决…...

Java 16进制 10进制 2进制数 相互的转换

在 Java 中&#xff0c;进行进制之间的转换时&#xff0c;除了功能的正确性外&#xff0c;效率和安全性也很重要。为了确保高效和相对安全的转换&#xff0c;我们通常需要考虑&#xff1a; 性能&#xff1a;使用内置的转换方法&#xff0c;如 Integer.toHexString()、Integer.…...

力扣动态规划-14【算法学习day.108】

前言 ###我做这类文章一个重要的目的还是给正在学习的大家提供方向&#xff08;例如想要掌握基础用法&#xff0c;该刷哪些题&#xff1f;建议灵神的题单和代码随想录&#xff09;和记录自己的学习过程&#xff0c;我的解析也不会做的非常详细&#xff0c;只会提供思路和一些关…...

数据结构day02

1 线性表的定义和基本操作 1.1 线性表的定义 分析&#xff1a; 1.1.1 问题一&#xff1a;我们为什么探讨线性表的定义和基本操作 在研究数据结构时&#xff0c;需要重点关注三个方面&#xff1a;逻辑结构、物理结构以及数据的运算。在本节内容里&#xff0c;我们首先来介绍线…...

随笔 | 写在一月的最后一天

. 前言 这个月比预想中过的要快更多。突然回看这一个月&#xff0c;还有点不知从何提笔。 整个一月可以总结为以下几个关键词&#xff1a; 期许&#xff0c;保持期许出现休息 . 期许 关于期许&#xff0c;没有什么时候比一年伊始更适合设立目标和计划的了。但令人惭愧的…...

JVM方法区

一、栈、堆、方法区的交互关系 二、方法区的理解: 尽管所有的方法区在逻辑上属于堆的一部分&#xff0c;但是一些简单的实现可能不会去进行垃圾收集或者进行压缩&#xff0c;方法区可以看作是一块独立于Java堆的内存空间。 方法区(Method Area)与Java堆一样&#xff0c;是各个…...

一文读懂fgc之cms

一文读懂 fgc之cms-实战篇 1. 前言 线上应用运行过程中可能会出现内存使用率较高&#xff0c;甚至达到95仍然不触发fgc的情况&#xff0c;存在内存打满风险&#xff0c;持续触发fgc回收&#xff1b;或者内存占用率较低时触发了fgc&#xff0c;导致某些接口tp99&#xff0c;tp…...

MYSQL 商城系统设计 商品数据表的设计 商品 商品类别 商品选项卡 多表查询

介绍 在开发商品模块时&#xff0c;通常使用分表的方式进行查询以及关联。在通过表连接的方式进行查询。每个商品都有不同的分类&#xff0c;每个不同分类下面都有商品规格可以选择&#xff0c;每个商品分类对应商品规格都有自己的价格和库存。在实际的开发中应该给这些表进行…...

HTB:Administrator[WriteUP]

目录 连接至HTB服务器并启动靶机 信息收集 使用rustscan对靶机TCP端口进行开放扫描 将靶机TCP开放端口号提取并保存 使用nmap对靶机TCP开放端口进行脚本、服务扫描 使用nmap对靶机TCP开放端口进行漏洞、系统扫描 使用nmap对靶机常用UDP端口进行开放扫描 使用nmap对靶机…...

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

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

【项目实战】通过多模态+LangGraph实现PPT生成助手

PPT自动生成系统 基于LangGraph的PPT自动生成系统&#xff0c;可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析&#xff1a;自动解析Markdown文档结构PPT模板分析&#xff1a;分析PPT模板的布局和风格智能布局决策&#xff1a;匹配内容与合适的PPT布局自动…...

Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!

一、引言 在数据驱动的背景下&#xff0c;知识图谱凭借其高效的信息组织能力&#xff0c;正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合&#xff0c;探讨知识图谱开发的实现细节&#xff0c;帮助读者掌握该技术栈在实际项目中的落地方法。 …...

LLM基础1_语言模型如何处理文本

基于GitHub项目&#xff1a;https://github.com/datawhalechina/llms-from-scratch-cn 工具介绍 tiktoken&#xff1a;OpenAI开发的专业"分词器" torch&#xff1a;Facebook开发的强力计算引擎&#xff0c;相当于超级计算器 理解词嵌入&#xff1a;给词语画"…...

大数据学习(132)-HIve数据分析

​​​​&#x1f34b;&#x1f34b;大数据学习&#x1f34b;&#x1f34b; &#x1f525;系列专栏&#xff1a; &#x1f451;哲学语录: 用力所能及&#xff0c;改变世界。 &#x1f496;如果觉得博主的文章还不错的话&#xff0c;请点赞&#x1f44d;收藏⭐️留言&#x1f4…...

中医有效性探讨

文章目录 西医是如何发展到以生物化学为药理基础的现代医学&#xff1f;传统医学奠基期&#xff08;远古 - 17 世纪&#xff09;近代医学转型期&#xff08;17 世纪 - 19 世纪末&#xff09;​现代医学成熟期&#xff08;20世纪至今&#xff09; 中医的源远流长和一脉相承远古至…...

【Linux手册】探秘系统世界:从用户交互到硬件底层的全链路工作之旅

目录 前言 操作系统与驱动程序 是什么&#xff0c;为什么 怎么做 system call 用户操作接口 总结 前言 日常生活中&#xff0c;我们在使用电子设备时&#xff0c;我们所输入执行的每一条指令最终大多都会作用到硬件上&#xff0c;比如下载一款软件最终会下载到硬盘上&am…...

协议转换利器,profinet转ethercat网关的两大派系,各有千秋

随着工业以太网的发展&#xff0c;其高效、便捷、协议开放、易于冗余等诸多优点&#xff0c;被越来越多的工业现场所采用。西门子SIMATIC S7-1200/1500系列PLC集成有Profinet接口&#xff0c;具有实时性、开放性&#xff0c;使用TCP/IP和IT标准&#xff0c;符合基于工业以太网的…...

Sklearn 机器学习 缺失值处理 获取填充失值的统计值

💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 使用 Scikit-learn 处理缺失值并提取填充统计信息的完整指南 在机器学习项目中,数据清…...

2025-06-01-Hive 技术及应用介绍

Hive 技术及应用介绍 参考资料 Hive 技术原理Hive 架构及应用介绍Hive - 小海哥哥 de - 博客园https://cwiki.apache.org/confluence/display/Hive/Home(官方文档) Apache Hive 是基于 Hadoop 构建的数据仓库工具&#xff0c;它为海量结构化数据提供类 SQL 的查询能力&#xf…...