POJ-2559 維護單調棧.細節阿細節

      這題意思很簡單...就是給一排并列寬為1,長度輸入資料的圖像..問能找到的最大矩形面積是多大...

      思路也很簡單...基本架構是: 從一邊做到另一邊..維護一個單調的棧..棧頂的矩形邊最長..棧底的最短...目前掃到某個位置的矩形..就判斷彈棧..直道棧頂的矩形長小于等于目前矩形..

      但是..細節阿...首先...不是從一邊做到另一邊就完了..還要從另一邊再做回來~~要做兩次才能得到結果...再一個...注意這種情況阿..:

       3 2 1 2

      判斷的時候稍不細心答案就是2了...但顯然答案是3的說...因為在做的時候..首先是2進棧..然後到1..但是1又把2彈掉了...發現開始的處理顯然是欠考慮的...雖然長度為2的是要出棧..但是2的這個位置不能丢棄..要記錄傳遞給第2位的1~~~~

program:

#include<iostream>
#include<string.h>
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<queue>
using namespace std;  
struct node
{
      __int64 h,s;     
}mystack[100005]; 
__int64 ans,x,k,n,p,a[100005],t;
int main()
{   
      freopen("input.txt","r",stdin);
      freopen("output.txt","w",stdout);   
      while (~scanf("%I64d",&n))
      {
            if (!n) break;
            ans=0;
            for (p=1;p<=n;p++) scanf("%I64d",&a[p]);
            a[0]=a[n+1]=0; n++;
            k=0;
            for (p=1;p<=n;p++)
            { 
                  x=a[p];
                  t=p; 
                  while (k && mystack[k].h>=x)
                  {
                        if (mystack[k].h*(p-mystack[k].s)>ans)
                            ans=mystack[k].h*(p-mystack[k].s);
                        if (mystack[k].s<t) t=mystack[k].s;
                        k--;
                  }
                  if (!k || mystack[k].h!=x) 
                  { 
                        k++; 
                        mystack[k].h=x;  
                        mystack[k].s=t; 
                  }  
            }  
            k=0;
            for (p=n-1;p>=0;p--)
            {
                  x=a[p]; 
                  t=p;
                  while (k && mystack[k].h>=x)
                  {
                        if (mystack[k].h*(mystack[k].s-p)>ans)
                            ans=mystack[k].h*(n-mystack[k].s-p);
                        if (mystack[k].s>t) t=mystack[k].s;
                        k--;
                  } 
                  if (!k || mystack[k].h!=x) 
                  { 
                        k++; 
                        mystack[k].h=x;  
                        mystack[k].s=t;   
                  }                  
            }  
            printf("%I64d\n",ans);
      } 
      return 0;
}