poj2559 Largest Rectangle in a Histogram

题意：　求最大矩形面积。

思路：　维护单调递增的矩形高度，当出现不能维护单调性的数加入时，开始维护面积累计ans

　　ans = max{ans , 当前矩形高度×当前位置到最右的宽度}；

最后再加入０，清空栈。

ps:跪jzt学长／。

 1 #include <stdio.h>
 2 #include <algorithm>
 3 using namespace std;
 4 struct node{
 5     long long  height, width;
 6 }stack[100010];
 7 long long n, height, top, tmp, ans;
 8 int main(){
 9     while (scanf("%lld", &n)!=EOF&&n){
10         top= 0;ans = 0;height = 0;
11         for (int i = 1; i <= n; i++){
12             scanf("%lld", &height); tmp = 0;
13             while (top > 0 && stack[top].height > height){ans = max (ans , stack[top].height * (tmp +stack[top].width));tmp += stack[top].width;top--;}
14             stack[++top].height = height;
15             stack[top].width = 1 + tmp;
16         }
17         tmp = 0;
18         while (top > 0){ans = max (ans , stack[top].height * (tmp +stack[top].width));tmp += stack[top].width;top--;}
19         printf("%lld
", ans);
20     }
21 }