代码随想录算法训练营day60 | 单调栈 84.柱状图中最大的矩形
创始人
2025-05-28 19:12:20

84.柱状图中最大的矩形

题目链接
解题思路：
本地单调栈的解法和接雨水的题目是遥相呼应的。

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

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

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

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

我来举一个例子，如图：
在这里插入图片描述
只有栈里从大到小的顺序，才能保证栈顶元素找到左右两边第一个小于栈顶元素的柱子。

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

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

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

除了栈内元素顺序和接雨水不同，剩下的逻辑就都差不多了。

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

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

C++代码如下：

class Solution {
public:int largestRectangleArea(vector& heights) {int result = 0;stack st;heights.insert(heights.begin(), 0); // 数组头部加入元素0heights.push_back(0); // 数组尾部加入元素0st.push(0);// 第一个元素已经入栈，从下标1开始for (int i = 1; i < heights.size(); i++) {if (heights[i] > heights[st.top()]) { // 情况一st.push(i);} else if (heights[i] == heights[st.top()]) { // 情况二st.pop(); // 这个可以加，可以不加，效果一样，思路不同st.push(i);} else { // 情况三while (!st.empty() && heights[i] < heights[st.top()]) { // 注意是whileint mid = st.top();st.pop();if (!st.empty()) {int left = st.top();int right = i;int w = right - left - 1;int h = heights[mid];result = max(result, w * h);}}st.push(i);}}return result;}
};
词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：L3-018 森森美图(计算几何+dijkstra)

下一篇：5.输入/输出

相关内容

热门资讯

测试管理之路 —— 如何优化测...   😏作者简介：博主是一位测试管理者，同时也是一名对...
底层原理计划--MySQL Mysql 存储引擎：mylsam/Innob/memoery…. Show engi...
文献阅读（49）—— 基于Tr... 文献阅读（49）—— 基于Transformer青光眼预测 文章目录文献...
你是真的“C”——实用memo... 你是真的“C”——各种实用memory类库函数的详细实现过程😎前言🙌...
[linux] Linux中环... 学校的服务器信息如下命令可以查询： cat /etc/redhat-release ...
计算机底层：奇偶校验码 计算机底层：奇偶校验码校验码的作用：在数据传输或存储时，可...
JavaWeb——urlPat... 1.一个Servlet配置多个访问路径  在WebServlet的配置里面urlPattern的类型...
指针 指针数组 数组指针 二级... 一、本文研究： 指针数组 与 二级指针 数组 与 数组指针 上面的两两一对࿰...
Ubuntu20 + KVM虚... 1 命令汇总 # 查看一下linux是32位还是64位：file /bin/ls # ...
Spring Boot 整合 ... Spring Boot 整合 RabbitMQ 多种消息模式 准备工作集成 RabbitMQ发布/订...
【BEV】TPVFormer复... 1. 前言 在环视图像的网络中，常使用鸟瞰图来进行特征提取，尽管比体素表...
华测RTK参数/华测GPS/华... 1.i93 视觉RTK华测导航i93视觉RTK是集成了华测目前新型视觉技术的一款革新型视觉RTK产品...
西瓜视频登录页面 题目 代码 登录页面td{width: 160px;height: ...
Android kotlin ... 文章目录 一、什么是SharedPreferences1、将数据存储到SharedPreferenc...
算法训练营day53_动态规划... 算法训练营day53_动态规划（3.17提前写） 1143.最长公共子序...
案例23-服务出现频繁掉线情况 目录 一、背景介绍 二、分析原因 1.nacos中data文件的作用 2. data路径下prot...
【文心一言】什么是文心一言，如... 文心一言什么是文心一言怎么获得内测资格接下来就给大家展示一下文学创作商业文案创作数理逻辑推算中文理解...
第31篇：Java流和文件操作... 目录 1、读取控制台输入流 1.1 从控制台读取多字符输入流 1.2 从控制台读取字符串流 2、读写...
Linux/Debian/Ub... 文章目录前言相关资源下载OpenCVCUDA下载CUDNN下载编译错误异常 前言 本文用来记录在l...
虚拟数字人和GPT-4的结合，... 最近，ChatGPT一直在互联网上狂飙，从 去年11月底推出到月活过亿&...
第三章 Liunx的常用命令 文章目录一、Liunx常用命令查看内存 free -m回到根目录 直接 cd 回车回到上一级目录 c...
素人做课会踩的3大坑，你中了几... 素人做课会踩的3大坑，你中了几个？大坑：盲目模仿别人做课的...
element输入框el-in... element输入框el-input之格式控制 （1）限制输入的长度&#...
oracle19c迁移手册 windows10- 查看当前用户所有的表：select table_name fro...
docker-compose搭... # 关闭防火墙 systemctl stop firewalld.service # 永久关闭防火墙...
【2023最新Activiti... 1.流程实例 1.1 什么是流程实例 流程实例(ProcessInstance)代表流程定义的执行实...
基于ggdensity包的等高... 简介 科研过程中，需要绘制某个后验密度/其他的形状。在发表论文中常常使用等高线来满足该...
Leetcode 105. 从... 题目： 给定两个整数数组 preorder 和 inorder ，其中 ...
点亮LED 目录 一、LED 硬件控制方式 二、LED 应用程序 1、定义宏 2、main函数 ①、打开文件  ...
随想008：烂摊子 我看到过很多离谱的现象。比如： 程序 代码重复、命名随意、逻辑混乱、甚至对齐都不一致&...