单调栈入门题

单调栈的题， 不知道是不是模板。。。

思想很重要， 保证栈内元素递增， 一旦单调性被破坏， 一直取出栈内元素并进行计算， 直到满足单调性， 成功的将模拟时的复杂计算进行简化与转化。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
#include<vector>
#include<set>
#include<cmath>
#include<cstdlib>
#include<ctime>
using namespace std;
typedef long long ll;

const int mx = 1e6 + 50;
const int inf = 1e9;

inline void fre(){ freopen("sign1.in", "r", stdout); freopen("sign1.out", "w", stdout); }

ll st[mx], top, w[mx], a[mx];
int n;

int main(){
    //fre();
    while(scanf("%d", &n) == 1 && n) {
    	top = 0;
    	ll ans = 0;
    	for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    	a[n+1] = 0;
    	
    	for(int i = 1; i <= n+1; i++) {
    		if(a[i] > st[top]) st[++top] = a[i], w[top] = 1;
    		else{
    			int width = 0;
    			while(a[i] <= st[top] && top){
    				width += w[top];
    				ans = max(ans, (ll)width * st[top]);
    				top--;
				}
				st[++top] = a[i]; w[top] = width+1;
			}
		}
		cout << ans << endl;
	}
	return 0;
}