题目描述
给定 $n$ 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。
求在该柱状图中,能够勾勒出来的矩形的最大面积。
以上是柱状图的示例,其中每个柱子的宽度为 1,给定的高度为 [2,1,5,6,2,3]
。
图中阴影部分为所能勾勒出的最大矩形面积,其面积为 10
个单位。
样例
输入: [2,1,5,6,2,3]
输出: 10
算法1
(单调栈) $O(n)$
可以观察到对于每个柱子而言它能构成的最大矩形的宽度由左右两边第一个比它小的柱子的位置而决定。而求某一个点左右两边第一个比它大/小的元素是单调栈的经典应用。
朴素的做法是头尾分别扫描两次,用一个 严格 单调递增的栈求出每个柱子左右两边 第一个 严格小于它的柱子的位置,对于数组的两边我们可以想象成各有一个无限小的柱子。
之后再遍历一遍数组求出答案。
C++ 代码
class Solution {
public:
int largestRectangleArea(vector<int>& height) {
int n = height.size();
vector<int> left(n, -1), right(n, n);
stack<int> stk;
for (int i = 0; i < n; i ++ )
{
while (!stk.empty() && height[stk.top()] >= height[i])
stk.pop();
if (!stk.empty()) left[i] = stk.top();
stk.push(i);
}
stk = stack<int>();
for (int i = n - 1; i >= 0; i -- )
{
while (!stk.empty() && height[stk.top()] >= height[i])
stk.pop();
if (!stk.empty()) right[i] = stk.top();
stk.push(i);
}
int res = 0;
for (int i = 0; i < n; i ++ )
res = max(res, (right[i] - left[i] - 1) * height[i]);
return res;
}
};
算法2
(单调栈) $O(n)$
也可以只扫描一遍来得出答案,思路与 LeetCode 42. Trapping Rain Water 类似,可以观察到我们不用找到每个柱子左右两边第一个严格小于它的柱子,我们用一个 非严格 单调递增的栈对每个柱子求出左边第一个小于等于
和右边第一个小于
的柱子的位置,同样可以计算出答案,这样对于连续相同的柱子,只有最左边的柱子的值才是真正意义上的最大值(对该高度的柱子而言)。
对称的我们也可以找到每个柱子左边第一个小于
和右边第一个小于等于
的柱子的位置,这样对于连续相同的柱子是最右边的柱子贡献了答案。将代码中heights[stk.top()] > heights[i]
改为heights[stk.top()] >= heights[i]
即可。
另外对于这种做法需要在数组后添加一个最小值使得所有数都能被弹出栈,比如输入数组正好是单调递增的情况。
C++ 代码
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
heights.push_back(-1);
int res = 0;
stack<int> stk;
for (int i = 0; i < heights.size(); i ++ )
{
while (stk.size() && heights[stk.top()] > heights[i])
{
int h = heights[stk.top()];
stk.pop();
if (stk.empty())
res = max(res, h * i);
else
res = max(res, h * (i - stk.top() -1));
}
stk.push(i);
}
return res;
}
};