LeetCode题解合集
题目描述
给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。
求在该柱状图中,能够勾勒出来的矩形的最大面积。
以上是柱状图的示例,其中每个柱子的宽度为 1,给定的高度为 [2,1,5,6,2,3]
。
图中阴影部分为所能勾勒出的最大矩形面积,其面积为 10
个单位。
示例:
输入: [2,1,5,6,2,3]
输出: 10
题解:
思考暴力解法:对每个位置 h[i]
,向左右分别查找最近比它小的位置,假设分别是 l
和 r
,那么以 h[i]
为高度的最大面积就是: (r-l-1) * h[i]
。
暴力的时间复杂度妥妥的 $O(n^2)$ 。。。
那么怎么快速高效查找左右的第一个比它小的元素位置呢?
可以使用单调栈。
考虑这样一个情况:假设 i < j < k 且 h[i] < h[j] < h[k]
,那么遍历到 k
位置时,k
左边最近的且比它小的肯定不会是 i
,因为 i
在 j
左边。
时间复杂度:$O(n)$
额外空间复杂度:$O(n)$
法一:
使用两个数组 left
和 right
分别保存每个位置左边和右边最近的比它小的元素的位置。
可以使用迭代法查找:
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int n = heights.size();
heights.push_back( -1 );
vector<int> left(n), right(n);
left[0] = -1;
int k;
for ( int i = 1; i < n; ++i ) {
k = i - 1;
while ( k >= 0 && heights[k] >= heights[i] )
k = left[k];
left[i] = k;
}
right[n - 1] = n;
for ( int i = n - 2; i >= 0; --i ) {
k = i + 1;
while ( k < n && heights[k] >= heights[i] )
k = right[k];
right[i] = k;
}
int ret = 0;
for ( int i = 0; i < n; ++i )
ret = max( ret, (right[i] - left[i] - 1) * heights[i]);
return ret;
}
};
/*
时间:116ms,击败:36.97%
内存:64.6MB,击败:15.53%
*/
也可以使用单调栈来查找:
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int n = heights.size();
vector<int> left(n), right(n);
vector<int> stk;
for ( int i = 0; i < n; ++i ) {
while (stk.size() && heights[stk.back()] >= heights[i] )
stk.pop_back();
left[i] = stk.size() ? stk.back() : -1;
stk.push_back( i );
}
stk.clear();
for ( int i = n - 1; i >= 0; --i ) {
while ( stk.size() && heights[stk.back()] >= heights[i] )
stk.pop_back();
right[i] = stk.size() ? stk.back() : n;
stk.push_back( i );
}
int ret = 0;
for ( int i = 0; i < n; ++i )
ret = max( ret, (right[i] - left[i] - 1) * heights[i]);
return ret;
}
};
/*
时间:140ms,击败:27.58%
内存:64.7MB,击败:14.88%
*/
法二:
使用递增的单调栈维护左边的元素,对于当前的位置 i
,如果 h[i] < h[stk.top()]
,说明栈顶元素找到了右边第一个比它小的元素,因为栈中的元素从栈底到栈顶是单调递增的,所以栈顶的下一个元素是栈顶左边第一个比它小的元素,这样就找到了栈顶元素的左右边界,可以求得以栈顶为高度的最大矩形面积。这种做法相当于固定右边界,从右往左枚举栈中那些大于 h[i]
元素的左边界。
注意:在 heights
末尾添加一个无穷小,可以保证最后栈中的所有元素都出栈,方便操作。
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int n = heights.size();
heights.push_back( -1 );
vector<int> stk;
int ret = 0, top, gap;
for ( int i = 0; i <= n; ++i ) {
while ( stk.size() && heights[stk.back()] > heights[i] ) {
top = stk.back();
stk.pop_back();
if ( stk.size() ) gap = i - stk.back() - 1;
else gap = i;
ret = max( ret, heights[top] * gap );
}
stk.push_back( i );
}
return ret;
}
};
/*
时间:104ms,击败:38.32%
内存:60.1MB,击败:34.29%
*/