这就是前几篇已经提到的求最大长方形那道题。
解题思路：
如果每次都向前向后扫描，有时会重复扫描多次，导致超时。
我们可以用一个单调栈 (类似单调队列) 由低到高来存储它的高度，并用数组对每个高度记录一下它前面一共有多少个比它高的，可以看做它的左宽。
按顺序考虑每个高度h，如果h大于栈顶元素，则入栈，此时它大于左面全部的元素（下文会提到为什么可以这样认为），所以将它的宽度初始为1。
否则，将栈内元素出栈，直到满足上面的条件。出栈时，我们要将出栈元素对问题的影响全部考虑进行处理，才能保证做法的正确性。
对于每个高度，它的作用无非两个：1、以自己作高，向外扩展 2、以别人作高，自己被扩展
【当以自己作高完毕以后，它的高度就没有什么意义了，为了方便，我们可以把它的高度看做与之后栈顶元素相等。
所以之后的栈顶元素可以看做是大于左面全部的元素。】此举只为容易理解，如不懂请跳过。
由于我们数组中已经记录了某个高度的左宽，所以我们只需要考虑它能不能向右扩展，如果能，能扩展多少？
首先，对于第一个出栈的元素来说，它的右宽一定是0。
然而对于第二个，它的右边有刚才出栈的元素，而且刚才出栈元素的总宽中所涉及的元素一定可以被自己扩展，所以自己的右宽为刚才出栈元素的总宽。 www.2cto.com
同理可知，第三个出栈元素的右宽为第二个出栈元素的总宽。依次类推。
而当h大于栈顶元素时，h的左宽应该是上次出栈元素的总宽+1（自己），然后入栈。
最后时，将所有元素出栈，即可将所有情况考虑。
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;
}
Read full article from HDU 1506 Largest Rectangle in a Histogram（最大长方形） - c++语言程序开发技术文章_c++编程 - 红黑联盟
解题思路：
如果每次都向前向后扫描，有时会重复扫描多次，导致超时。
我们可以用一个单调栈 (类似单调队列) 由低到高来存储它的高度，并用数组对每个高度记录一下它前面一共有多少个比它高的，可以看做它的左宽。
按顺序考虑每个高度h，如果h大于栈顶元素，则入栈，此时它大于左面全部的元素（下文会提到为什么可以这样认为），所以将它的宽度初始为1。
否则，将栈内元素出栈，直到满足上面的条件。出栈时，我们要将出栈元素对问题的影响全部考虑进行处理，才能保证做法的正确性。
对于每个高度，它的作用无非两个：1、以自己作高，向外扩展 2、以别人作高，自己被扩展
【当以自己作高完毕以后，它的高度就没有什么意义了，为了方便，我们可以把它的高度看做与之后栈顶元素相等。
所以之后的栈顶元素可以看做是大于左面全部的元素。】此举只为容易理解，如不懂请跳过。
由于我们数组中已经记录了某个高度的左宽，所以我们只需要考虑它能不能向右扩展，如果能，能扩展多少？
首先，对于第一个出栈的元素来说，它的右宽一定是0。
然而对于第二个，它的右边有刚才出栈的元素，而且刚才出栈元素的总宽中所涉及的元素一定可以被自己扩展，所以自己的右宽为刚才出栈元素的总宽。 www.2cto.com
同理可知，第三个出栈元素的右宽为第二个出栈元素的总宽。依次类推。
而当h大于栈顶元素时，h的左宽应该是上次出栈元素的总宽+1（自己），然后入栈。
最后时，将所有元素出栈，即可将所有情况考虑。
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;
}
Read full article from HDU 1506 Largest Rectangle in a Histogram（最大长方形） - c++语言程序开发技术文章_c++编程 - 红黑联盟
