当前位置: 首页 > 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 产品服务创新以…...

<6>-MySQL表的增删查改

目录 一&#xff0c;create&#xff08;创建表&#xff09; 二&#xff0c;retrieve&#xff08;查询表&#xff09; 1&#xff0c;select列 2&#xff0c;where条件 三&#xff0c;update&#xff08;更新表&#xff09; 四&#xff0c;delete&#xff08;删除表&#xf…...

《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》

引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...

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

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

pam_env.so模块配置解析

在PAM&#xff08;Pluggable Authentication Modules&#xff09;配置中&#xff0c; /etc/pam.d/su 文件相关配置含义如下&#xff1a; 配置解析 auth required pam_env.so1. 字段分解 字段值说明模块类型auth认证类模块&#xff0c;负责验证用户身份&am…...

【Go】3、Go语言进阶与依赖管理

前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课&#xff0c;做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程&#xff0c;它的核心机制是 Goroutine 协程、Channel 通道&#xff0c;并基于CSP&#xff08;Communicating Sequential Processes&#xff0…...

什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南

文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/55aefaea8a9f477e86d065227851fe3d.pn…...

【Oracle】分区表

个人主页&#xff1a;Guiat 归属专栏&#xff1a;Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...

laravel8+vue3.0+element-plus搭建方法

创建 laravel8 项目 composer create-project --prefer-dist laravel/laravel laravel8 8.* 安装 laravel/ui composer require laravel/ui 修改 package.json 文件 "devDependencies": {"vue/compiler-sfc": "^3.0.7","axios": …...

华硕a豆14 Air香氛版,美学与科技的馨香融合

在快节奏的现代生活中&#xff0c;我们渴望一个能激发创想、愉悦感官的工作与生活伙伴&#xff0c;它不仅是冰冷的科技工具&#xff0c;更能触动我们内心深处的细腻情感。正是在这样的期许下&#xff0c;华硕a豆14 Air香氛版翩然而至&#xff0c;它以一种前所未有的方式&#x…...

html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码

目录 一、&#x1f468;‍&#x1f393;网站题目 二、✍️网站描述 三、&#x1f4da;网站介绍 四、&#x1f310;网站效果 五、&#x1fa93; 代码实现 &#x1f9f1;HTML 六、&#x1f947; 如何让学习不再盲目 七、&#x1f381;更多干货 一、&#x1f468;‍&#x1f…...