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
| class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int sz = heights.size();
vector<int> left(sz);
vector<int> right(sz);
left[0] = -1;
right.back() = sz;
for(int i = 1; i < sz; ++i)
{
int p = i - 1;
while(p >= 0 && heights[p] >= heights[i])
p = left[p];
left[i] = p;
}
for(int i = sz - 2; i >= 0; -- i)
{
int p = i + 1;
while(p < sz && heights[p] >= heights[i])
p = right[p];
right[i] = p;
}
int ret = 0;
for(int i = 0; i < sz; ++i)
ret = max(ret, heights[i] * (right[i] - left[i] - 1));
return ret;
}
};
|
每个位置的最大矩形是其(right - left) * cur_height，而左边可以通过遍历查找离他最远且值>=他本身的坐标，右边也可通过遍历查找离他最远的且一路上值>=它本身的坐标。但如果对每个坐标都进行一次左右遍历就会消耗太多计算量。
此时可以采用dp
设想，对于先前查找过的元素，比如p<i，如果p是符合条件heights[p] >= heights[i]的，那么p的左边界也必然是符合这个条件的，由此可以进行坐标的跳跃，将下一迭代的p = left[p]，道理则依次。所以每个查找都可以运用到之前到查找的信息。总体来说仅仅为O(n)，对于右边界来说则同理。
使用stack
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
heights.push_back(-1);
stack<int> s;
int ret = 0;
for(int i = 0; i < heights.size(); ++i)
{
while(!s.empty() && heights[i] < heights[s.top()])
{
auto h = heights[s.top()];
s.pop();
ret = max(ret, (i - (s.empty() ? -1 : s.top()) - 1) * h);
}
s.push(i);
}
return ret;
}
};
|
维持stack为上升序列，每碰到之前比他大的就pop掉，因为你如果比他小了，那么对于你这个柱子来说的最大矩形的高度必定受限于你而不是他，之前所有比你大的pop掉后的真空区域就是这个的面积。而循环中的i为右界，取不到，stack.top()，为左界，也取不到，中间的就是所有比你大的。上升队列的每2个之间都会有一个真空区域，而面积必定为区域宽度x右边。 
why stack?