【单调栈]LeetCode84: 柱状图中最大的矩形

2023-12-16 08:12

本文主要是介绍【单调栈]LeetCode84: 柱状图中最大的矩形,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

作者推荐

【动态规划】【广度优先搜索】LeetCode:2617 网格图中最少访问的格子数

本文涉及的知识点

单调栈

题目

给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。
求在该柱状图中,能够勾勒出来的矩形的最大面积。
示例 1:
输入:heights = [2,1,5,6,2,3]
输出:10
解释:最大的矩形为图中红色区域,面积为 10
示例 2:
输入: heights = [2,4]
输出: 4
参数
1 <= heights.length <=105
0 <= heights[i] <= 104

分析

时间复杂度😮(n)。

枚举

如何不重复不遗漏的枚举所有子数组,最容易想到的枚举子数组的起点和终点[left,right]。这样的时间复杂度是O(n2),超时。 可以枚举子数组的最小高度heights[i],再枚举left[i],right[i]。left[i]的取值范围(x1,i]。x1是从i-1到0,第一个heights[x1]<heights[i],如果不存在,令x1等于-1。right[i]的取值范围[i,x2)。x2是从i+1,到n-1 第一个heights[x2] <= heights[i],如果不存在,令x2等于m_c。由于要求最大面积,所以left[i]取最小值,right[i]取最大值。即:矩形最底低在i时,宽度最大的子数组为(left[i],right[i])。
x1是小于,x2是小于等于的含义是:如果有多个最低处,以最右边的为准。
符合以下三个条件:

两个子状态都有序
新增的数据有序
查询有序

vLeftHeightIndex

vLeftHeightIndex记录下标和高度。如果i1 < i2,且heights[i1] >= heights[i2],则i1被淘汰了。淘汰后,下标升序,高度也升序。新增加的数据下标也是按升序加入,这是可以优化成单调栈(向量)的条件。
vLeftHeightIndex.back() 被淘汰,说明heights[i]小于等于vLeftHeightIndex.back(),而且是第一个小于等于的高度。也就是vRight。

代码,

核心代码

class Solution {
public:int largestRectangleArea(vector<int>& heights) {m_c = heights.size();vector<pair<int, int>> vLeftHeightIndex;vector<int> vLeftFirstLess(m_c,-1), vRightFirstMoreEqual(m_c,m_c);//别忘记初始化for (int i = 0; i < m_c; i++){while (vLeftHeightIndex.size() && (heights[i]  <= vLeftHeightIndex.back().first )){vRightFirstMoreEqual[vLeftHeightIndex.back().second] = i;vLeftHeightIndex.pop_back();				}if (vLeftHeightIndex.size()){vLeftFirstLess[i] = vLeftHeightIndex.back().second;}vLeftHeightIndex.emplace_back(heights[i], i);}int iRet = 0;for (int i = 0; i < m_c; i++){iRet = max(iRet, heights[i] * (vRightFirstMoreEqual[i] - vLeftFirstLess[i] - 1));}return iRet;}int m_c;
};

测试用例

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{if (v1.size() != v2.size()){assert(false);return;}for (int i = 0; i < v1.size(); i++){assert(v1[i] == v2[i]);}
}template<class T>
void Assert(const T& t1, const T& t2)
{assert(t1 == t2);
}int main()
{vector<int> heights;int r;{Solution slu;		heights = { 2, 1, 5, 6, 2, 3 };auto res = slu.largestRectangleArea(heights);Assert(10, res);}{Solution slu;heights = { 2,4 };auto res = slu.largestRectangleArea(heights);Assert(4, res);}
}

2023年3月旧代码

class Solution {
public:
int largestRectangleArea(vector& heights) {
m_c = heights.size();
vector vMaxLeft;
{
vector<std::pair<int, int>> vLeft;
for (int i = 0; i < heights.size(); i++)
{
const int& h = heights[i];
const int iLessNum = std::lower_bound(vLeft.begin(), vLeft.end(), h, [](const std::pair<int, int>& p, const int i)
{
return p.first < i;
}) - vLeft.begin();
if (0 == iLessNum)
{
vMaxLeft.push_back(-1);
}
else
{
vMaxLeft.push_back(vLeft[iLessNum - 1].second);
}
while (vLeft.size() && (vLeft.back().first >= h))
{
vLeft.pop_back();
}
vLeft.emplace_back(h, i);
}
}
int iMax = INT_MIN;
{
vector<std::pair<int, int>> vRight;
for (int i = m_c - 1; i >= 0; i–)
{
const int& h = heights[i];
const int iLessNum = std::lower_bound(vRight.begin(), vRight.end(), h+1, [](const std::pair<int, int>& p, const int i)
{
return p.first < i;
}) - vRight.begin();
if (0 == iLessNum)
{
iMax =max(iMax, h * (m_c - vMaxLeft[i]-1));
}
else
{
const int iRight = vRight[iLessNum - 1].second;
iMax = max(iMax, h * (iRight - vMaxLeft[i]-1));
}
while (vRight.size() && (vRight.back().first >= h))
{
vRight.pop_back();
}
vRight.emplace_back(h, i);
}
}
return iMax;
}
int m_c;
};

2023年8月

class Solution {
public:
int largestRectangleArea(vector& heights) {
m_c = heights.size();
vector vLeft(m_c, -1), vRight(m_c, m_c);
stack sta;
for (int i = 0; i < heights.size(); i++)
{
while (sta.size() && (heights[i] <= heights[sta.top()] ))
{
vRight[sta.top()] = i;
sta.pop();
}
if (sta.size())
{
vLeft[i] = sta.top();
}
sta.emplace(i);
}
int iRet = 0;
for (int i = 0; i < m_c; i++)
{
iRet = max(iRet, (vRight[i] - vLeft[i] - 1) * heights[i]);
}
return iRet;
}
int m_c;
};

扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关

下载

想高屋建瓴的学习算法,请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话
闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙,那算法就是他的是睛

测试环境

操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。

这篇关于【单调栈]LeetCode84: 柱状图中最大的矩形的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/499783

相关文章

poj 3723 kruscal,反边取最大生成树。

题意: 需要征募女兵N人,男兵M人。 每征募一个人需要花费10000美元,但是如果已经招募的人中有一些关系亲密的人,那么可以少花一些钱。 给出若干的男女之间的1~9999之间的亲密关系度,征募某个人的费用是10000 - (已经征募的人中和自己的亲密度的最大值)。 要求通过适当的招募顺序使得征募所有人的费用最小。 解析: 先设想无向图,在征募某个人a时,如果使用了a和b之间的关系

poj 3258 二分最小值最大

题意: 有一些石头排成一条线,第一个和最后一个不能去掉。 其余的共可以去掉m块,要使去掉后石头间距的最小值最大。 解析: 二分石头,最小值最大。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <c

poj 2175 最小费用最大流TLE

题意: 一条街上有n个大楼,坐标为xi,yi,bi个人在里面工作。 然后防空洞的坐标为pj,qj,可以容纳cj个人。 从大楼i中的人到防空洞j去避难所需的时间为 abs(xi - pi) + (yi - qi) + 1。 现在设计了一个避难计划,指定从大楼i到防空洞j避难的人数 eij。 判断如果按照原计划进行,所有人避难所用的时间总和是不是最小的。 若是,输出“OPETIMAL",若

poj 2135 有流量限制的最小费用最大流

题意: 农场里有n块地,其中约翰的家在1号地,二n号地有个很大的仓库。 农场有M条道路(双向),道路i连接着ai号地和bi号地,长度为ci。 约翰希望按照从家里出发,经过若干块地后到达仓库,然后再返回家中的顺序带朋友参观。 如果要求往返不能经过同一条路两次,求参观路线总长度的最小值。 解析: 如果只考虑去或者回的情况,问题只不过是无向图中两点之间的最短路问题。 但是现在要去要回

poj 2594 二分图最大独立集

题意: 求一张图的最大独立集,这题不同的地方在于,间接相邻的点也可以有一条边,所以用floyd来把间接相邻的边也连起来。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <sta

poj 3422 有流量限制的最小费用流 反用求最大 + 拆点

题意: 给一个n*n(50 * 50) 的数字迷宫,从左上点开始走,走到右下点。 每次只能往右移一格,或者往下移一格。 每个格子,第一次到达时可以获得格子对应的数字作为奖励,再次到达则没有奖励。 问走k次这个迷宫,最大能获得多少奖励。 解析: 拆点,拿样例来说明: 3 2 1 2 3 0 2 1 1 4 2 3*3的数字迷宫,走两次最大能获得多少奖励。 将每个点拆成两个

poj 3692 二分图最大独立集

题意: 幼儿园里,有G个女生和B个男生。 他们中间有女生和女生认识,男生男生认识,也有男生和女生认识的。 现在要选出一些人,使得这里面的人都认识,问最多能选多少人。 解析: 反过来建边,将不认识的男生和女生相连,然后求一个二分图的最大独立集就行了。 下图很直观: 点击打开链接 原图: 现图: 、 代码: #pragma comment(

最大流、 最小费用最大流终极版模板

最大流  const int inf = 1000000000 ;const int maxn = 20000 , maxm = 500000 ;struct Edge{int v , f ,next ;Edge(){}Edge(int _v , int _f , int _next):v(_v) ,f(_f),next(_next){}};int sourse , mee

二分最大匹配总结

HDU 2444  黑白染色 ,二分图判定 const int maxn = 208 ;vector<int> g[maxn] ;int n ;bool vis[maxn] ;int match[maxn] ;;int color[maxn] ;int setcolor(int u , int c){color[u] = c ;for(vector<int>::iter

最大流=最小割=最小点权覆盖集=sum-最大点权独立集

二分图最小点覆盖和最大独立集都可以转化为最大匹配求解。 在这个基础上,把每个点赋予一个非负的权值,这两个问题就转化为:二分图最小点权覆盖和二分图最大点权独立集。   二分图最小点权覆盖     从x或者y集合中选取一些点,使这些点覆盖所有的边,并且选出来的点的权值尽可能小。 建模:     原二分图中的边(u,v)替换为容量为INF的有向边(u,v),设立源点s和汇点t