单调栈求最大面积

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.

 

Sample Input

7 2 1 4 5 1 3 3

4 1000 1000 1000 1000

0

 

Sample Output

8

4000

给出n（n<=100000）个木板的高度，宽度均为1，将n个木板竖成一排，在上面截取长方形，求最大面积。

 

#include<stdio.h>
#include<stack>
using namespace std;
__int64 rec[100010];
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF && n!=0)
    {
        stack<int> s;//栈一直保持着坐标对应的值单调递增,4,5,7,8 来了个6,最后4,5,6

        __int64 max_area=0,sum=0;//保存着最大的面积
        for(int i=0;i<n;i++)
        {
            scanf("%I64d",&rec[i]);
        }
        rec[n]=-1;
        int temp_index;
        for(int j=0;j<=n;j++)
        {
            if(s.empty()||rec[s.top()]<rec[j])//先把大于栈顶的弄进栈
                s.push(j);//j对应高度所在的坐标，rec[j]对应它的高度
            else if(rec[s.top()]>rec[j])//相等的直接跳过,j-s.top()已经可以计算
            {
                while(!s.empty() && rec[s.top()]>rec[j])
                {
                    sum=(j-s.top())*rec[s.top()];//不断向左扩展，看图
                    if(max_area<sum)
                        max_area=sum;
                    temp_index=s.top();
                    s.pop();
                }
                s.push(temp_index);
//重新开始,此时temp_index下标表示以rec[j]为高度的矩形的左边的边界（因为盏是递减的，所以左边的比右边的高）
                rec[temp_index] = rec[j];
//这里注意理解，把rec[j]的值赋值给rec[temp](原来的高度已经没用了),此时它表示的是高为rec[j]的矩形
            }

        }
        printf("%I64d\n",max_area);

    }
    return 0;
}