求直方图的最大面积
使用栈结构来解决这个问题。始终保持栈内的数据为单增，如果不是，出栈并计算。
参考：
http://blog.csdn.net/doc_sgl/article/details/11805519
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
|
class Solution {
public:
int largestRectangleArea(vector<int> &height) {
if(height.size() <= 0) return 0;
height.push_back(-1);
int max = 0x80000000;
vector<int> stack;
stack.clear();
stack.push_back(0);
for(int i = 1; i < height.size(); i++) {
if(height[stack[stack.size()-1]] <= height[i]) stack.push_back(i);
else {
while(stack.size() > 0 && height[stack[stack.size() - 1]] > height[i]) {
int heighttmpi = stack[stack.size()-1];
stack.pop_back();
if(stack.size() == 0) {
if(height[heighttmpi] * (i-0) > max) max = height[heighttmpi] * (i-0);
}
else {
if(height[heighttmpi] * (i-stack[stack.size()-1]-1) > max) max = height[heighttmpi] * (i-stack[stack.size()-1]-1);
}
}
}
stack.push_back(i);
}
return max;
}
};
|