題意：
這就是前幾篇已經提到的求最大長方形那道題。
解題思路：
如果每次都向前向後掃描，有時會重復掃描多次，導致超時。
我們可以用一個單調棧 (類似單調隊列) 由低到高來存儲它的高度，並用數組對每個高度記錄一下它前面一共有多少個比它高的，可以看做它的左寬。
按順序考慮每個高度h，如果h大於棧頂元素，則入棧，此時它大於左面全部的元素（下文會提到為什麼可以這樣認為），所以將它的寬度初始為1。
否則，將棧內元素出棧，直到滿足上面的條件。出棧時，我們要將出棧元素對問題的影響全部考慮進行處理，才能保證做法的正確性。
對於每個高度，它的作用無非兩個：1、以自己作高，向外擴展 2、以別人作高，自己被擴展
【當以自己作高完畢以後，它的高度就沒有什麼意義了，為了方便，我們可以把它的高度看做與之後棧頂元素相等。
所以之後的棧頂元素可以看做是大於左面全部的元素。】此舉只為容易理解，如不懂請跳過。
由於我們數組中已經記錄了某個高度的左寬，所以我們只需要考慮它能不能向右擴展，如果能，能擴展多少？
首先，對於第一個出棧的元素來說，它的右寬一定是0。
然而對於第二個，它的右邊有剛才出棧的元素，而且剛才出棧元素的總寬中所涉及的元素一定可以被自己擴展，所以自己的右寬為剛才出棧元素的總寬。 www.2cto.com
同理可知，第三個出棧元素的右寬為第二個出棧元素的總寬。依次類推。
而當h大於棧頂元素時，h的左寬應該是上次出棧元素的總寬+1（自己），然後入棧。
最後時，將所有元素出棧，即可將所有情況考慮。
[cpp]
#include <stdio.h>
#define max(a,b) a > b ? a : b
#define N 100005
int q[N]={-1},w[N]; //w記錄的是從這個點開始，之前有幾個高度大於等於此高度.
int main()
{
int n,h;
while(scanf("%d",&n),n)
{
int top = 0;
__int64 ans = 0;
for(int i=1;i<=n+1;i++)
{
if(i != n+1)
scanf("%d",&h);
else
h = 0;
if(h > q[top])
q[++top] = h , w[top] = 1;
else
{
__int64 cnt = 0;
while(h <= q[top])
{
ans = max(ans ,(cnt+w[top])*q[top] );
cnt += w[top--];
}
q[++top] = h;
w[top] = cnt+1;
}
}
printf("%I64d\n",ans);
}
return 0;
}
作者：dgq8211
