单调栈

Largest Rectangle in a Histogram

经典题

单调栈：保持栈内元素单调递增
因为如果递减 后面的元素的高度就会替换前面的元素的高度
前面元素等价于多个后面元素
当有新元素加入是将原先的递增序列从后往前更新答案
最后使得栈保持原有性质

这样可以保证每个元素只会被考虑一次，不用重复向前查找第一个低于的

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std ;

typedef long long ll ;
const int N = 1000010 ;

int n ;
int a[N] ;
stack <pair<int, int> > s ;
ll ans ;

int main() {
	while (scanf("%d", &n)) {
		if (n == 0) break ;
		for (int i = 1; i <= n; i++) scanf("%d", &a[i]) ;
		a[++n] = 0 ;
		while (!s.empty()) s.pop() ;
		ans = 0 ;
		s.push(make_pair(a[1], 1)) ;
		for (int i = 2; i <= n; i++) {
			if (a[i] >= s.top().first) s.push(make_pair(a[i], 1)) ; 
			else {
				int wd = 0 ;
				while (!s.empty() && s.top().first > a[i]) {
					wd += s.top().second ;
					ans = max(ans, 1ll * wd * s.top().first) ;
					s.pop() ;
				}
				s.push(make_pair(a[i], wd + 1)) ;
			}
		}
		printf("%lld\n", ans) ;
	}    
}