HDU 1506 Largest Rectangle in a Histogram（最大长方形）

题意：
这就是前几篇已经提到的求最大长方形那道题。
解题思路：
如果每次都向前向后扫描，有时会重复扫描多次，导致超时。
我们可以用一个单调栈 (类似单调队列) 由低到高来存储它的高度，并用数组对每个高度记录一下它前面一共有多少个比它高的，可以看做它的左宽。
按顺序考虑每个高度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