直方图中最大的矩形

题目

对于一个坐标 \(i\) 的 高度 \(h_i\) , 如果你想跨过他组建矩形 ， 那么后面的高度肯定不会大于 \(h_i\) , 由于后面的高度未知 , 一种更

加优秀的思想是固定一个坐标 \(i\) , 我们从后往前拼凑直到遇到一个高度比它小的 , （ 这里贪心地想 , 高度确定的话 , 宽度尽可能宽)

对于每个高度 \(i\) , 都经历相同的子问题 , 其实就把所有的情况枚举了 , 只每次只枚举了有效状态.

#include
#include
#include
using namespace std;
const int N = 1e5+5 ;

long long ans;
int n , h[N] , q[N] , width[N];

int main()
{
	while(1)
	{
		scanf("%d",&n);
		if( !n ) break;
		
		ans = 0;
		
		for(int i=1;i<=n;++i)
			scanf("%d",&h[i]);
			
		int r = 0;
		h[n+1] = 0 , q[0] = 0 , width[0] = 0;
		
		for(int i=1;i<=n+1;++i)
		{
			int w = 0;
			while(q[r] > h[i])	
			{
				w += width[r];
				ans = max(ans , (long long)w*q[r]);
				--r;
			}
			q[++r] = h[i] , width[r] = w+1;
		}
		printf("%lld\n",ans);
	}	
	return 0;
}