LeetCode力扣84.柱状图中最大的矩形(C++)【单调栈】详细解析+代码注释
2022/1/26 22:04:17
本文主要是介绍LeetCode力扣84.柱状图中最大的矩形(C++)【单调栈】详细解析+代码注释,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
LeetCode力扣84.柱状图中最大的矩形
题目描述
给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。求在该柱状图中,能够勾勒出来的矩形的最大面积。
输入输出样例
输入 #1
6 2 1 5 6 2 3
输出 #1
10
解释:最大的矩形为图中红色区域,面积为 10
解题思路
首先第一眼可以看出本题用暴力法一定可以做出来,但纯暴力一般会超时,可以借助单调栈对暴力法进行优化。
先说暴力法,最外层循环遍历 n 根柱子,内部对每根柱子左右分别进行 while 循环找到第一根高度小于当前高度的柱子,就可以算出以当前柱子为高时矩形的最大面积,遍历结束即可找出矩形最大面积。
单调栈法,依旧是最外层循环遍历 n 根柱子,并且只在栈中存储高度递增的柱子的数组下标。比如第 i 根柱子的高度大于栈顶的柱子高度时,就让i入栈,小于栈顶柱子高度,说明以栈顶为高的矩形找到了右边界,而栈中存储的是递增的序列,那么左边界也确定了,左右边界做差就得到了矩形的宽,那么以栈顶为高的矩形的最大面积就确定了,将面积与之前记录的最大面积进行比较,更新最大面积。遍历结束就得到了最终结果。这样就省去了纯暴力中每次循环查找左右边界的过程。光看文字看不懂,这里建议看代码画图自己模拟一遍。
要注意的是最外层遍历要多执行一次,for(int i=0;i<=n;i++),下标为 n 的数组中存柱子高度为0,因为如果出现 n 根柱子高度恰好为递增序列的情况,那么程序不会对最大面积进行更新。
代码
此代码不支持上机检测。
#include<iostream> #include<algorithm> #include<stack> using namespace std; int n; //柱子数量 int max_area; //记录当前最大面积 int area; //记录以当前柱子为高的最大面积 int height[100005]; //存储柱子高度 stack<int> s; //存储高度递增的柱子的数组下标 int main() { cin>>n; for(int i=0;i<n;i++) cin>>height[i]; for(int i=0;i<=n;i++) { while(!s.empty()&&height[s.top()]>height[i]) //栈非空且第i根柱子高度栈顶柱子高度,此时不能入栈,开始计算面积 { if(s.size()==1) area=height[s.top()]; //当栈中仅有一个元素,矩形高为柱子高度宽为1 else area=height[s.top()]*(i-s.top()); //当栈中有多个元素,矩形高为栈顶柱子高度,宽为左右第一个比当前柱子矮的两柱子的间距即i-s.top max_area=max(max_area,area); //与之前记录的最大面积作比较,更新最大面积 s.pop(); //已做过高的柱子出栈 } s.push(i); //栈空或者栈顶柱子高度小于第i根柱子高度,下标入栈 } cout<<max_area; return 0; }
这篇关于LeetCode力扣84.柱状图中最大的矩形(C++)【单调栈】详细解析+代码注释的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升
- 2024-05-08代码报错不用愁,CodeGeeX一键完成代码修复、错误解释的功能上线了!