Largest Rectangle in a Histogram

Time Limit: 1000MS      Memory Limit: 65536K

来源：
poj：poj 2559 Largest Rectangle in a Histogram
vjudge：E-Largest Rectangle in a Histogram
参考博客：http://blog.csdn.net/alongela/article/details/8230739

单调栈

Description

A histogram is a polygon composed of a sequence of rectangles aligned at a common base line. The rectangles have equal widths but may have different heights. For example, the figure on the left shows the histogram that consists of rectangles with the heights 2, 1, 4, 5, 1, 3, 3, measured in units where 1 is the width of the rectangles: 

Usually, histograms are used to represent discrete distributions, e.g., the frequencies of characters in texts. Note that the order of the rectangles, i.e., their heights, is important. Calculate the area of the largest rectangle in a histogram that is aligned at the common base line, too. The figure on the right shows the largest aligned rectangle for the depicted histogram.

Input

The input contains several test cases. Each test case describes a histogram and starts with an integer n, denoting the number of rectangles it is composed of. You may assume that 1<=n<=100000. Then follow n integers h1,...,hn, where 0<=hi<=1000000000. These numbers denote the heights of the rectangles of the histogram in left-to-right order. The width of each rectangle is 1. A zero follows the input for the last test case.

Output

For each test case output on a single line the area of the largest rectangle in the specified histogram. Remember that this rectangle must be aligned at the common base line.

Sample Input

7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0

Sample Output

8
4000

Hint

Huge input, scanf is recommended.

题意：
输入一个数n，接着输入n个数，表示矩形的长，单位矩形的宽都为1，矩形可在同等高度内联通，求所组成矩形的最大面积并输出。

解题思路

利用单调栈，此题建立一个单调递减栈（从上到下单调递减！！）每个元素进栈一次，出栈一次，在出栈的时候更新现下的矩形面积；
先以2 1 4 5 1 3 3 为例：
设（h,w）---(高，宽)
1. （2,1）入栈
2.（1,1）入栈，因为2>1,故（2,1）出栈，更新面积s=2*1=2；累计当前栈为（1,2）；
3.（4,1）入栈，因为1<4，故不用出栈，s不用更新；
4.（5,1）入栈，因为4<5，故不用出栈，s不用更新；
5.（1,1）入栈，因为5>1，故（5,1）出栈，s=5*1=5，累计当前栈，有（1,2）（4,2），由于4>1，故（4,2）出栈，更新面积s=4*2=8；累计当前栈有（1，4）；由于1=1，故（1,4）出栈，因为s'=1*5=5<s=8，故s不更新；累计当前栈为（1，5）；
6.(3,1)入栈，因为1<3，故不用出栈，s不用更新；
7.（3,1）入栈，因为3=3，所以（3,1）出栈，s'=1*3<s=8，故不更新s，累计当前栈为（1,5）（3,2）；
8.最后将所有元素出栈，先出栈（3,2），由于s'=3*2=6<s=8，故s不更新，累计当前栈为（1,7）；
9.出栈（1,7），s'=1*7<s=8，故不更新s；
10.栈空，输出最终最大面积s=8；

完整代码：

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define ll long long
struct node
{
    ll height;
    ll width;
};
node stack[100010];
int main()
{
    ll n,m;
    while(scanf("%lld",&n),n)
    {
        ll top=0,w,s,ans=0;
        for(int i=0;i<n;i++)
        {
            w=0;
            scanf("%lld",&m);
            while(top>0&&stack[top-1].height>=m)
            {
                s=stack[top-1].height*(stack[top-1].width+w);
                ans=max(ans,s);
                w+=stack[top-1].width;
                top--;
            }
            stack[top].height=m;
            stack[top].width=w+1;
            top++;
        }
        w=0;
        while(top>0)
        {
            s=stack[top-1].height*(stack[top-1].width+w);
            ans=max(ans,s);
            w+=stack[top-1].width;
            top--;
        }
        printf("%lld\n",ans);
    }
    return 0;
}