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

代码随想录算法训练营 | day60 单调栈 84.柱状图中最大的矩形

刷题

84.柱状图中最大的矩形

题目链接 | 文章讲解 | 视频讲解

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

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

  • 1 <= heights.length <=10^5

  • 0 <= heights[i] <= 10^4

思路及实现

42. 接雨水 是找每个柱子左右两边第一个大于该柱子高度的柱子,而本题是找每个柱子左右两边第一个小于该柱子的柱子。

这里就涉及到了单调栈很重要的性质,就是单调栈里的顺序,是从小到大还是从大到小

在题解42. 接雨水中我讲解了接雨水的单调栈从栈头(元素从栈头弹出)到栈底的顺序应该是从小到大的顺序。

那么因为本题是要找每个柱子左右两边第一个小于该柱子的柱子,所以从栈头(元素从栈头弹出)到栈底的顺序应该是从大到小的顺序!

我来举一个例子,如图:

只有栈里从大到小的顺序,才能保证栈顶元素找到左右两边第一个小于栈顶元素的柱子。

所以本题单调栈的顺序正好与接雨水反过来。

此时大家应该可以发现其实就是栈顶和栈顶的下一个元素以及要入栈的三个元素组成了我们要求最大面积的高度和宽度

理解这一点,对单调栈就掌握的比较到位了。

除了栈内元素顺序和接雨水不同,剩下的逻辑就都差不多了,在题解42. 接雨水 我已经对单调栈的各个方面做了详细讲解,这里就不赘述了。

主要就是分析清楚如下三种情况:

  • 情况一:当前遍历的元素heights[i]大于栈顶元素heights[st.top()]的情况

  • 情况二:当前遍历的元素heights[i]等于栈顶元素heights[st.top()]的情况

  • 情况三:当前遍历的元素heights[i]小于栈顶元素heights[st.top()]的情况

代码如下:

class Solution {int largestRectangleArea(int[] heights) {Stack<Integer> st = new Stack<Integer>();// 数组扩容,在头和尾各加入一个元素int [] newHeights = new int[heights.length + 2];newHeights[0] = 0;newHeights[newHeights.length - 1] = 0;for (int index = 0; index < heights.length; index++){newHeights[index + 1] = heights[index];}heights = newHeights;st.push(0);int result = 0;// 第一个元素已经入栈,从下标1开始for (int i = 1; i < heights.length; i++) {// 注意heights[i] 是和heights[st.top()] 比较 ,st.top()是下标if (heights[i] > heights[st.peek()]) {st.push(i);} else if (heights[i] == heights[st.peek()]) {st.pop(); // 这个可以加,可以不加,效果一样,思路不同st.push(i);} else {while (heights[i] < heights[st.peek()]) { // 注意是whileint mid = st.peek();st.pop();int left = st.peek();int right = i;int w = right - left - 1;int h = heights[mid];result = Math.max(result, w * h);}st.push(i);}}return result;}
}

相关文章:

代码随想录算法训练营 | day60 单调栈 84.柱状图中最大的矩形

刷题 84.柱状图中最大的矩形 题目链接 | 文章讲解 | 视频讲解 题目&#xff1a;给定 n 个非负整数&#xff0c;用来表示柱状图中各个柱子的高度。每个柱子彼此相邻&#xff0c;且宽度为 1 。 求在该柱状图中&#xff0c;能够勾勒出来的矩形的最大面积。 1 < heights.len…...

vscode中vue项目报错

当在vscode中写代码时&#xff0c;报错报错报错......... 已经头大&#xff0c;还没写就报错&#xff0c; 这是因为eslint对语法的要求太过严格导致的编译时&#xff0c;出现各种语法格式错误 我们打开vue.config.js&#xff0c;加上这句代码&#xff0c;就OK啦 lintOnSave:…...

「数据结构」二叉树2

&#x1f387;个人主页&#xff1a;Ice_Sugar_7 &#x1f387;所属专栏&#xff1a;初阶数据结构 &#x1f387;欢迎点赞收藏加关注哦&#xff01; 文章目录 &#x1f349;前言&#x1f349;链式结构&#x1f349;遍历二叉树&#x1f34c;前序遍历&#x1f34c;中序遍历&#x…...

数据处理系列课程 01:谈谈数据处理在数据分析中的重要性

一、数据分析 可能很多朋友第一次听到这个名词&#xff0c;那么我们先来谈一谈什么是数据分析。 数据分析是指用适当的统计分析方法对收集来的大量数据进行分析&#xff0c;将它们加以汇总和理解&#xff0c;以求最大化地开发数据的功能&#xff0c;发挥数据的作用。数据分析是…...

C++卡码网题目55--右旋字符串

卡码网题目链接 字符串的右旋转操作是把字符串尾部的若干个字符转移到字符串的前面。给定一个字符串 s 和一个正整数 k&#xff0c;请编写一个函数&#xff0c;将字符串中的后面 k 个字符移到字符串的前面&#xff0c;实现字符串的右旋转操作。 例如&#xff0c;对于输入字符…...

八股文打卡day8——计算机网络(8)

面试题&#xff1a;什么是强缓存和协商缓存&#xff1f; 我的回答&#xff1a; 强缓存&#xff1a;浏览器不需要发送请求到服务器&#xff0c;直接从浏览器缓存中获取数据。浏览器不需要和服务器进行交互就可以获取数据&#xff0c;这样极大提高了页面访问速度。 协商缓存&am…...

亚马逊推出 Graviton4:具有 536.7 GBps 内存带宽的 96 核 ARM CPU

如今&#xff0c;许多云服务提供商都设计自己的芯片&#xff0c;但亚马逊网络服务 (AWS) 开始领先于竞争对手&#xff0c;目前其子公司 Annapurna Labs 开发的处理器可以与 AMD 和英特尔的处理器竞争。本周&#xff0c;AWS 推出了 Graviton4 SoC&#xff0c;这是一款基于 ARM 的…...

跨域问题的解决

1.什么是跨域&#xff1f; 浏览器从一个域名的网页去请求另外一个域名的资源时&#xff0c;域名、端口或者协议不同都是跨域 2.跨域的解决方案 设置CORS响应头∶后端可以在HTTP响应头中添加相关的CORS标头&#xff0c;允许特定的源&#xff08;域名、协议、端口)访问资源。S…...

Typro+PicGo自动上传图片(图床配置)

文章目录 所需工具主要配置 TyproPicGo自动上传图片&#xff08;图床配置&#xff09; 使用Typro编写 的markdown(md)文件如果存在图片&#xff0c;并且想快速发布博文的话&#xff0c;常使用PiGO工具配置图床服务器来管理图片。 所需工具 TyporaPicGo(依赖Nodejs和插件super…...

uniapp实战 -- 个人信息维护(含选择图片 uni.chooseMedia,上传文件 uni.uploadFile,获取和更新表单数据)

效果预览 相关代码 页面–我的 src\pages\my\my.vue <!-- 个人资料 --><view class"profile" :style"{ paddingTop: safeAreaInsets!.top px }"><!-- 情况1&#xff1a;已登录 --><view class"overview" v-if"membe…...

企业如何建立价值评估体系?

企业绩效评价体系是指由一系列与绩效评价相关的评价制度、评价指标体系、评价方法、评价标准以及评价机构等形成的有机整体。企业的评价系统大致可以分为以下四个层次&#xff1a; 第一、岗位评价系统&#xff0c;主要针对不同岗位之间的评估。例如&#xff0c;企业中一般业务…...

华为安防监控摄像头

华为政企42 华为政企 目录 上一篇华为政企城市一张网研究报告下一篇华为全屋wifi6蜂鸟套装标准...

[node] Node.js 缓冲区Buffer

[node] Node.js 缓冲区Buffer 什么是BufferBuffer 与字符编码Buffer 的方法概览Buffer 的实例Buffer 的创建写入缓冲区从 Buffer 区读取数据将 Buffer 转换为 JSON 对象Buffer 的合并Buffer 的比较Buffer 的覆盖Buffer 的截取--sliceBuffer 的长度writeUIntLEwriteUIntBE 什么是…...

【ARM Cortex-M 系列 5 -- RT-Thread renesas/ra4m2-eco 移植编译篇】

文章目录 RT-Thread 移植编译篇编译os.environ 使用示例os.putenv使用示例python from 后指定路径 编译问题_POSIX_C_SOURCE 介绍编译结果 RT-Thread 移植编译篇 本文以瑞萨的ra4m2-eco 为例介绍如何下载rt-thread 及编译的设置。 RT-Thread 代码下载&#xff1a; git clone …...

功能强大的开源数据中台系统 DataCap 1.18.0 发布

推荐一套基于 SpringBoot 开发的简单、易用的开源权限管理平台&#xff0c;建议下载使用: https://github.com/devlive-community/authx 推荐一套为 Java 开发人员提供方便易用的 SDK 来与目前提供服务的的 Open AI 进行交互组件&#xff1a;https://github.com/devlive-commun…...

A Philosophy of Software Design 学习笔记

前言 高耦合&#xff0c;低内聚&#xff0c;降低复杂度&#xff1a;在软件迭代中&#xff0c;不关注软件系统结构&#xff0c;导致软件复杂度累加&#xff0c;软件缺乏系统设计&#xff0c;模块混乱&#xff0c;一旦需求增加、修改或者优化&#xff0c;改变的代价无法评估&…...

设计模式----解释器模式

一、简介 解释器模式使用频率并不高&#xff0c;通常用来构建一个简单语言的语法解释器&#xff0c;它只在一些非常特定的领域被用到&#xff0c;比如编译器、规则引擎、正则表达式、sql解析等。 解释器模式是行为型设计模式之一&#xff0c;它的原始定义为&#xff1a;用于定义…...

Linux常用命令(一):Conda、RPM、文件权限、apt-get(更新中...

文章目录 一、Conda二、RPM三、文件权限四、apt-get 一、Conda Conda是一个开源的软件包管理系统和环境管理系统&#xff0c;用于安装和管理软件包及其依赖项。它主要用于Python编程语言&#xff0c;但也可以用于其他语言的项目。Conda可以帮助用户创建不同版本的Python环境&a…...

3 个适用于 Mac 电脑操作的 Android 数据恢复最佳工具 [附步骤]

在当今的数字时代&#xff0c;无论是由于意外删除、系统故障还是其他原因&#xff0c;从 Android 设备中丢失数据不仅会带来不便&#xff0c;而且会造成非常严重的后果。特别是对于Mac用户来说&#xff0c;从Android手机恢复数据是一个很大的麻烦。幸运的是&#xff0c;随着许多…...

日志服务 SLS 深度解析:拥抱云原生和 AI,基于 SLS 的可观测分析创新

云布道师 10 月 31 日&#xff0c;杭州云栖大会上&#xff0c;日志服务 SLS 研发负责人简志和产品经理孟威等人发表了《日志服务 SLS 深度解析&#xff1a;拥抱云原生和 AI&#xff0c;基于 SLS 的可观测分析创新》的主题演讲&#xff0c;对阿里云日志服务 SLS 产品服务创新以…...

[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解

突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 ​安全措施依赖问题​ GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...

逻辑回归:给不确定性划界的分类大师

想象你是一名医生。面对患者的检查报告&#xff08;肿瘤大小、血液指标&#xff09;&#xff0c;你需要做出一个**决定性判断**&#xff1a;恶性还是良性&#xff1f;这种“非黑即白”的抉择&#xff0c;正是**逻辑回归&#xff08;Logistic Regression&#xff09;** 的战场&a…...

相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)

【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...

深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南

&#x1f680; C extern 关键字深度解析&#xff1a;跨文件编程的终极指南 &#x1f4c5; 更新时间&#xff1a;2025年6月5日 &#x1f3f7;️ 标签&#xff1a;C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言&#x1f525;一、extern 是什么&#xff1f;&…...

AGain DB和倍数增益的关系

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

省略号和可变参数模板

本文主要介绍如何展开可变参数的参数包 1.C语言的va_list展开可变参数 #include <iostream> #include <cstdarg>void printNumbers(int count, ...) {// 声明va_list类型的变量va_list args;// 使用va_start将可变参数写入变量argsva_start(args, count);for (in…...

系统掌握PyTorch:图解张量、Autograd、DataLoader、nn.Module与实战模型

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文通过代码驱动的方式&#xff0c;系统讲解PyTorch核心概念和实战技巧&#xff0c;涵盖张量操作、自动微分、数据加载、模型构建和训练全流程&#…...

前端开发者常用网站

Can I use网站&#xff1a;一个查询网页技术兼容性的网站 一个查询网页技术兼容性的网站Can I use&#xff1a;Can I use... Support tables for HTML5, CSS3, etc (查询浏览器对HTML5的支持情况) 权威网站&#xff1a;MDN JavaScript权威网站&#xff1a;JavaScript | MDN...

如何把工业通信协议转换成http websocket

1.现状 工业通信协议多数工作在边缘设备上&#xff0c;比如&#xff1a;PLC、IOT盒子等。上层业务系统需要根据不同的工业协议做对应开发&#xff0c;当设备上用的是modbus从站时&#xff0c;采集设备数据需要开发modbus主站&#xff1b;当设备上用的是西门子PN协议时&#xf…...

EEG-fNIRS联合成像在跨频率耦合研究中的创新应用

摘要 神经影像技术对医学科学产生了深远的影响&#xff0c;推动了许多神经系统疾病研究的进展并改善了其诊断方法。在此背景下&#xff0c;基于神经血管耦合现象的多模态神经影像方法&#xff0c;通过融合各自优势来提供有关大脑皮层神经活动的互补信息。在这里&#xff0c;本研…...