【单调栈】POJ-2559 Largest Rectangle in a Histogram

Largest Rectangle in a Histogram

Time Limit: 1000MS

Memory Limit: 65536K

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.

Source

Ulm Local 2003

————————————————————蛋疼的分割线————————————————————

思路：首先想到了枚举的方法，自左至右枚举每一个可能的矩形。最后找到最大的。但是重复劳动非常多。换个方法吧。我们知道只有枚举到最后的时候，才能得到最大的矩形面积。也就是先进后出了！但是，需要注意的是，并不是单纯的先进后出。我们必须维护这个栈，使得栈内长方形高度始终递增。因为假使一个打破单调性的长方形入栈，前面的长方形便无法向后扩展了。无法扩展意味着我们需要计算出一个面积，它可能就是最大值。因此，每一次出现一个更高的长方形，放入栈内。直到遇见了更矮的长方形，此时维护这个单调栈，算出此时能得到的最大面积，计算完毕的长方形通通出栈。

代码如下：

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
struct Node{
    long long h;
    int cross;
}sta[100010];
int main(){
	int n;
	while(scanf("%d", &n) != EOF&&n){
        long long a[100010], MaxAr = 0, curAr, height;//MaxAr保存最大面积 curAr保存当前计算得到的最大面积
        int top = -1, pos;
        struct Node u;
        for(int i = 0; i < n; i++)
            scanf("%I64d", a+i);
        sta[++top].h = 0;  sta[top].cross = 0;//我们在栈首放置一个假想的高度为0的矩形，不必再判定栈是否为空。请看下面的出栈条件
        for(int i = 0; i <= n; i++){
            pos = i+1;//一定要保存当前长方形位置
            if(i == n)  height = 0;//当处理到最后一个长方形以后，要弹出栈内所有元素，height置为0,进入下面的while计算剩下元素分别能够构造的最大面积
            else  height = a[i];
            u.cross = pos;//中间值保存当前长方形。以备入栈。
            while(sta[top].h > height){//一直出栈直到回到第一个比当前长方形矮（或等高）的长方形
                u = sta[top--];//更新当前栈首元素，出栈
                curAr = (pos - u.cross) * u.h;//计算出栈后得到的矩形面积，注意，这里的计算不是简单的出去一个长方形计算一次，而是出去一个，算出它参与构成的最大矩形面积
                MaxAr = curAr > MaxAr ? curAr : MaxAr;//更新最大矩形面积
            }
            sta[++top].h = height;//当前长方形入栈
            sta[top].cross = u.cross;//注意！此处需要认真理解！为什么存的是u.cross而不是pos?储存u.cross，是因为它代表了从最后一个出栈的长方形开始直到当前pos为止，都可以构成一个矩形
        }

        printf("%I64d\n", MaxAr);
	}
	return 0;
}