Language:
题目：
Largest Rectangle in a Histogram
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 |
思路：
我们把每个数字都看成一个宽度为1，长度为a[i]的小矩形，我们从左向右遍历每一个小矩形，然后以这个小矩形向左向右扩展，所能向左扩展的最大值（下标）用L[i]记录下来，所能扩张的最大值（下标）用R[i]记录下来，并把所能扩展最大的矩形面积a[i]*(R[i]-L[i])记录下来，每遍历一个小矩形就动态的经行更新最大值，然后最后输出最后的值即可。
图文详解：
1） 刚开始栈中为空，压入下标0；然后当i=1时，2<=1不成立，下标出栈，栈变为空，计算此时面积res=2；
2）高度1,5,6是依次递增的，所以对应下标依次压入栈中；当i=4时，6>2，下标3出栈，所以计算此时的面积res=6，如图：
3）栈顶元素为2，其对应的高度为5>2（此时，还要和下标i=4的高度比较），所以，栈顶元素2出栈，计算面积为res=10；
4）因为栈顶元素为1，其对应的高度为1<2，满足条件，所以，将i入栈，直到i=6（为压入的0）；此时栈中的元素为{1,4,5}，有一个栈顶元素对应的高度大于i=6对应的高度，所以，5出栈，计算面积为3，其中最大面积为10；
5）栈顶元素为4，其对应高度为2>0，所以，2出栈，计算面积为4，最大面积为10；
6） 此时，栈顶元素为1，对应高度为1>0，所以，1出栈，因为1出栈以后，栈变为空，所以，计算面积的方式有变化，res=height[1]*6=6，最大面积为10。
代码如下：
代码：
#include<iostream>
#include<stdio.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+10;
ll a[maxn];
ll L[maxn],R[maxn];
int st[maxn];//栈的大小
int main(){
int n;
while(cin>>n&&n){
int t=0;
for(int i = 0;i < n;i++)
scanf("%lld",&a[i]);
for(int i=0;i<n;i++){
while(t>0&&a[st[t-1]]>=a[i]) t--;
L[i] = t==0?0:(st[t-1]+1);
st[t++] = i;
}
t = 0 ;
for(int i=n-1;i>=0;i--){
while(t>0&&a[st[t-1]]>=a[i]) t--;
R[i] =t ==0?n:(st[t-1]);
st[t++] = i;
}
ll res = 0;
for(int i = 0;i<n;i++){
res = max(res,a[i]*(R[i]-L[i]));
}
printf("%lld\n",res);
}
return 0;
}