题目链接：Largest Rectangle in Histogram
Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.
6
5 □
□ □
□ □ 3
2 □ □ 2 □
□ 1 □ □ □ □
□ □ □ □ □ □
Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].
6
5 □
■ ■
■ ■ 3
2 ■ ■ 2 □
□ 1 ■ ■ □ □
□ □ ■ ■ □ □
The largest rectangle is shown in the shaded area, which has area = 10 unit.
For example,
Given height = [2,1,5,6,2,3],
return 10.
这道题的要求是在直方图中找到面积最大的矩形。
直接的暴力的思路就是对于每一组子数组，找到其中最低的高度，然后求面积，进而求出最大的矩形面积。总共有n^2个子数组，找最低高度是O(n)的操作，所以复杂度是O(n^3)。
进一步，可以从每一个bar往两边走，以自己的高度为标准，直到两边低于自己的高度为止，然后用自己的高度乘以两边走的宽度得到矩阵面积。因为对于任意一个bar都计算了以自己为目标高度的最大矩阵，所以最好的结果一定会被取到。每次往两边走的复杂度是O(n)，总共有n个bar，所以时间复杂度是O(n^2)。
最后说说最优的解法，思路跟Longest Valid Parentheses类似，主要维护一个栈，这个栈从低向上的高度是依次递增的。如果遇到当前bar高度比栈顶元素低，那么就出栈直到栈顶元素低于当前bar，出栈过程中检测前面满足条件的矩阵：
- 如果栈已经为空，说明到目前为止所有元素（当前下标元素除外）都比出栈元素高度要大（否则栈中肯定还有元素），所以矩阵面积就是高度乘以当前下标i。
- 如果栈不为空，那么就是从当前栈顶元素的下一个到当前下标的元素之间都比出栈元素高度大（因为栈顶元素第一个比当前出栈元素小的），所以矩阵面积就是高度乘以当前下标i减栈顶元素再减1。
注意最后还要对剩下的栈做清空并且判断，因为每次是对于前面的元素面积进行判断，所以循环结束中如果栈中仍有元素，还是要继续判断面积直到栈为空。
时间复杂度：O(n)
空间复杂度：O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution
{
public:
int largestRectangleArea(vector<int> &height)
{
int res = 0;
stack<int> si;
for(int i = 0; i < height.size(); ++ i)
{
while(!si.empty() && height[si.top()] >= height[i])
{
int h = height[si.top()];
si.pop();
int s = h * (si.empty() ? i : (i - si.top() - 1));
res = max(res, s);
}
si.push(i);
}
while(!si.empty())
{
int h = height[si.top()];
si.pop();
int s = h * (si.empty() ? height.size() : (height.size() - si.top() - 1));
res = max(res, s);
}
return res;
}
};
其实，也可以实现在height的最后放入一个较小的数字作为哨兵元素，这样就能保证栈最后为空了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution
{
public:
int largestRectangleArea(vector<int> &height)
{
int res = 0;
stack<int> si;
height.push_back(0);
for(int i = 0; i < height.size(); ++ i)
{
while(!si.empty() && height[si.top()] >= height[i])
{
int h = height[si.top()];
si.pop();
int s = h * (si.empty() ? i : (i - si.top() - 1));
res = max(res, s);
}
si.push(i);
}
return res;
}
};