【单调栈]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(n²)，超时。可以枚举子数组的最小高度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

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