题目链接：https://vjudge.net/problem/POJ-2559

题意：

如图所示，求最大的连续阴影面积

思路：

首先我们肯定时可以暴力判断，找出每一个最大的向右扩展程度和向左扩展程度，然后求面积，最后再求个最大值，不过这样肯定会超时，不是一个好的解法。

这样我们就要想一个更有效的方法了，首先一个一个的判断会有很多的重复计算，如何避免掉这些重复的计算呢？假设现在又一组数据 

2 1 4 5 1 3 3 对应的下标为
1 2 3 4 5 6 7

以其中一个基准值为准 假设下标为2的1，它在向右扩展的过程中首先遇到的是4，4比1大可以继续向右扩展，接着是5，5比4大还可以继续向右扩展，然后是1，1比5小，所以你会发现5向右只能扩展到1，同理4也是，但是1还可以继续向右扩展一直到最后。也就是说我们可以发现在判断每一个小矩形的最大扩展其实只需要扫描一遍就行了。

有没有发现这个过程很符合栈的特点，其实我们也就是利用栈的后进先出的特点，每次向右扩展的时候如果大于等于当前栈顶元素就进栈，如果小于就说明当前栈顶元素最大扩展就是这个小于它的地方，然后栈顶元素出栈，接着判断下一个栈顶元素。

同理向左扩展也和向右扩展一样，我们只需要把数列从右向左扫描一遍就行了。

不过注意的是我们需要在最前和最后设置一个0，强制扫描结束。

#include <algorithm>
#include <iostream>
#include <stack>

using namespace std;
typedef long long LL;
const int N = 1e5+7;

// 分别记录第i个矩形的高度，向左扩展的最大位置-1, 向右扩展大最大位置+1
LL a[N], L[N], R[N];	
LL n;
stack<LL> st;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n;
	while(cin >> n, n)
	{
		for(int i = 1; i <= n; i++)
			cin >> a[i];
		a[0] = a[n+1] = 0;	// 设置边界
		for(int i = 1; i <= n+1; i++)
		{
			// 如果栈不空且向右扩展的下一个值小于当前栈顶
			while(!st.empty() && a[i] < a[st.top()])
			{
				R[st.top()] = i;
				st.pop();
			}
			st.push(i);		// 保存在栈内的是第i个矩形的下标
		}
		while(!st.empty())
			st.pop();
		for(int i = n; i >= 0; i--)
		{
			// 如果栈不空且向左扩展的下一个值小于当前栈顶
			while(!st.empty() && a[i] < a[st.top()])
			{
				L[st.top()] = i;
				st.pop();
			}
			st.push(i);
		}
		while(!st.empty())
			st.pop();
		LL ans = 0;
		for(int i = 1; i <= n; i++)
		{
			LL r = R[i] - 1;	
			LL l = L[i] + 1;
			ans = max(ans, a[i] * (r -l + 1));
		}
		cout << ans << '\n';
	}
	
	
	return 0;
}