week5 单调栈 最大矩形

Titile:给一个直方图，求直方图中的最大矩形的面积。
例如，下面这个图片中直方图的高度从左到右分别是2, 1, 4, 5, 1, 3, 3, 他们的宽都是1，其中最大的矩形是阴影部分。

Input:输入包含多组数据。每组数据用一个整数n来表示直方图中小矩形的个数，你可以假定1 <= n <= 100000. 然后接下来n个整数h1, …, hn, 满足 0 <= hi <= 1000000000. 这些数字表示直方图中从左到右每个小矩形的高度，每个小矩形的宽度为1。 测试数据以0结尾。

Output:对于每组测试数据输出一行一个整数表示答案。

样例：
Input:
7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0
output:
8
4000

分析：

• 对于所给直方图中的每个小矩形（初始时宽为1的矩形），如果能够向左右两端延伸，成为一个大矩形，且该大矩形是该小矩形向左右两端延伸的最大矩形。这个大矩形的高其实就是初始时小矩形的高，而只要求出向左右两边延伸的下标，即可计算出该大矩形的面积。而对于每个小矩形求一次大矩形，再在大矩形选出最大，即为直方图中的最大矩形。

• 对于每个初始时的小矩形，确定其延伸的左右端点。设初始时小矩形的高为high，左端点即为往左数第一个高度小于high的点，右端点即为往右数第一个高度小于high的点。

• 利用单调栈求左右端点。

• 单调栈分析：
  （1）建立一个数组用作栈，记录栈底和栈顶下标。先进后出。
  （2） 设每次要push进栈的元素为pushe，如果栈不为空且栈顶的元素大于pushe，弹出栈顶元素，直到栈顶元素小于等于pushe，最后将pushe压入栈。这个操作可以保证栈内元素的单调性。
  （3）在这个过程中，每次要push进来的元素为pushe，弹出的栈顶元素为pope。对于每个pope，pushe为pope往右遇到的第一个小于pushe的元素（这里的第一就是指遇到的第一个）。
  （4）而对于每个pushe，弹出栈顶操作完之后（需要弹出栈顶则弹出，不需要就直接进行接下来的操作），则当前的栈顶元素就是pushe往左第一个小于pushe的元素（这里的第一就是指遇到的第一个）。

• 使用数组a存储初始时的小矩阵，a[i]=high,代表第i个矩阵的高度为high。上述单调栈，栈中存放的是元素，而本次实际应用中存放的是元素的下标，这样是为了方便使用right，left数组与数组a的下标对应，例如元素a[i]的右端点即为right[i],左端点为left[i],计算时直接使用a[i]*(right[i]-left[i]-1)则可得到大矩形面积。

总结：注意最后的矩形面积应该为long long，int与int相乘使用long long来存储。

#include<stdio.h>
#define range 100000+10 
int n=0;
long long max=0;
long long a[range];
int st[range];//放下标，st[top]表示栈顶元素的下标
int right[range];
int left[range];
void fun()
{
 int bot=1,top=0;
 a[0]=0;a[n+1]=0;
 for(int i=1;i<=n+1;i++)
 {
  while(top>=bot&&a[st[top]]>a[i])
  {
   right[st[top]]=i;
   top--;
  }
  left[i]=st[top];
  st[++top]=i;
 }  
} 
void findmax()
{
 long long temp=0;
 for(int i=1;i<=n;i++)
 {
  temp=(long long)a[i]*(long long)(right[i]-left[i]-1);
  max=temp>max?temp:max;
 }
}
int main(){
 while(scanf("%d",&n)&&n!=0)
 {
  max=0;
  for(int i=1;i<=n;i++)
      scanf("%lld",&a[i]);
  fun();
//  for(int i=1;i<=n;i++)
//      printf("%d   ",right[i]);
//  printf("\n"); 
//  for(int i=1;i<=n;i++)
//      printf("%d   ",left[i]);
  findmax();
  printf("%lld\n",max);
 }
 return 0;
}