当前位置:网站首页>leetcode 84.柱状图中最大的矩形 单调栈应用
leetcode 84.柱状图中最大的矩形 单调栈应用
2022-08-10 19:06:00 【Alkali!】
题目描述
思路
首先,要想找到第 i i i 位置最大面积是什么?(这是本题的关键点,要知道怎么去计算面积!)
是以i 为中心,向左找第一个小于 h e i g h t s [ i ] heights[i] heights[i] 的位置 l e f t i left_i lefti;向右找第一个小于于 h e i g h t s [ i ] heights[i] heights[i] 的位置 r i g h t i right_i righti,即最大面积为 h e i g h t s [ i ] ∗ ( r i g h t i − l e f t i − 1 ) heights[i] * (right_i - left_i -1) heights[i]∗(righti−lefti−1),如下图所示:
那么如何找到每个位置 i i i的 l e f t i left_i lefti和 r i g h t i right_i righti呢?
这里我们利用单调栈的思想就行,可以实现 O ( n ) O(n) O(n)的复杂度。
直接看代码
代码
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
vector<int> left,right;
stack<pair<int,int>> s;
//求lefti
for(int i=0;i<heights.size();i++)
{
while(!s.empty()&&s.top().second>=heights[i])
s.pop();
if(s.empty())
left.push_back(-1); //如果找不到左边第一个比它小的,说明它是最小的,那直接拉到-1
else
left.push_back(s.top().first);
s.push({
i,heights[i]});
}
while(!s.empty()) s.pop(); //清空栈
//求righti
for(int i=heights.size()-1;i>=0;i--)
{
while(!s.empty()&&s.top().second>=heights[i])
s.pop();
if(s.empty())
right.push_back(heights.size());//如果找不到右边第一个比它小的,说明它是最小的,那直接拉到n
else
right.push_back(s.top().first);
s.push({
i,heights[i]});
}
reverse(right.begin(),right.end()); //答案得逆置一下
int res=0;
for(int i=0;i<heights.size();i++)
res=max(res,(right[i]-left[i]-1)*heights[i]); //求可能的最大面积
return res;
}
};
边栏推荐
猜你喜欢
【LeetCode】42、接雨水
铁蛋白-AHLL纳米颗粒|人表皮生长因子-铁蛋白重链亚基纳米粒子(EGF-5Cys-FTH1)|铁蛋白颗粒包载氯霉素Chloramphenicol-Ferritin
越折腾越好用的 3 款开源 APP
uni-app 数据上拉加载更多功能
Common ports and services
几行深度学习代码设计包含功能位点的候选免疫原、酶活性位点、蛋白结合蛋白、金属配位蛋白
状态压缩dp蒙德里安的梦想
赎金信问题答记
Modern Privacy-Preserving Record Linkage Techniques: An Overview论文总结
我们用48h,合作创造了一款Web游戏:Dice Crush,参加国际赛事
随机推荐
大家要的Biotin-PEG3-Br/acid/NHS ester/alcohol/amine合集分享
Pt/CeO2单原子纳米酶|[email protected] NPs纳米酶|碳纳米管负载铂颗粒纳米酶|白血病拮抗多肽修饰的FeOPtPEG复合纳米酶
你不知道的浏览器页面渲染机制
2022 Hangdian Multi-School Seven Black Magic (Sign-in)
一维数组动态和问题答记
[Natural Language Processing] [Vector Representation] PairSupCon: Pairwise Supervised Contrastive Learning for Sentence Representation
UnitTest中的Path must be within the project 问题
从 Delta 2.0 开始聊聊我们需要怎样的数据湖
力扣18-四数之和——双指针法
优化是一种习惯●出发点是'站在靠近临界'的地方
新建离线同步节点时选择数据去向-表时报错,数据库类型是adb pg,怎么办?
[教你做小游戏] 斗地主的手牌,如何布局?看25万粉游戏区UP主怎么说
「POJ 3666」Making the Grade 题解(两种做法)
cordova 安装错误 Command failed: powershell 解决方法
Site Architecture Detection & Chrome Plugin for Information Gathering
idea汉化教程[通俗易懂]
铁蛋白-AHLL纳米颗粒|人表皮生长因子-铁蛋白重链亚基纳米粒子(EGF-5Cys-FTH1)|铁蛋白颗粒包载氯霉素Chloramphenicol-Ferritin
Keras deep learning combat (17) - image segmentation using U-Net architecture
QoS服务质量六路由器拥塞管理
(十二) findContours函数的hierarchy详解