直方图最大矩阵面积

 1 #include <iostream>
 2 #include <stack>
 3 #include <algorithm>
 4 #include <cstring>
 5 using namespace std;
 6 
 7 int LargestRectangleArea(vector<int>& height){
 8     height.push_back(0);//为了统计，数组最后添加0，确保原数组的最后一位得到计算
 9     stack<int> s;
10     int LargestArea = 0;
11     int temp,i=0;
12     while(i<(int)height.size()){
13         if(s.empty()||(height[i]>height[s.top()])){
14             s.push(i);
15             i++;
16         }
17         else{
18             temp = s.top();
19             s.pop();
20             LargestArea = max(LargestArea,height[temp]*(s.empty()?i:i-s.top()-1));
21         }
22     }
23     return LargestArea;
24 }
25 int main()
26 {
27     int a[] ={2,1,5,6,2,3};
28     vector<int> height(a,a+sizeof(a)/sizeof(int));
29     cout<<LargestRectangleArea(height)<<endl;
30     return 0;
31 }