Histogram LightOJ - 1083

Histogram LightOJ - 1083

題意：給出一個直方圖，由n個長條組成，它們的x軸上坐標分別為1-n，讀入n之後讀入的一行中，第i個表示x軸上坐標為i的長條長度。求直方圖最大的正方形面積。

方法：

核心是求出每個長條向左右可以"擴展"的最大長度。

法一：單調棧

將n個元素的編號依次入棧。每次入棧前，設要入棧的編號為x，對應長度為l，將棧頂的編號對應的長度大於等於l的所有編號出棧（由於此題的一些特性，將“大於等於”改為“大於”也可以使用，但這不是標準的單調棧）。這之後，棧頂元素就是x能擴展到的最左端的端點減1（註意，是減1）。對於某個元素，其出棧的那一刻，使其出棧的x減一就是其能擴展到的最右側的端點。

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 int T,n,ans,len;
 5 int st[30100],a[30100],l[30100],r[30100];
 6 void push(int idx)
 7 {
 8     while(len>0&&a[st[len]]>a[idx])    r[st[len--]]=idx-1;
 9     l[idx]=st[len];
10     st[++len]=idx;
11 }
12 int main()
13 {
14     int i,TT;
15     scanf("%d",&T);
16     for(TT=1;TT<=T;TT++)
17     {
18         scanf("%d",&n);
19         for(i=1;i<=n;i++)
20             scanf("%d",&a[i]);
21         len=0;
22         ans=0;
23         for(i=1;i<=n;i++)
24             push(i);
25         while(len>0)    r[st[len--]]=n;
26         for(i=1;i<=n;i++)
27             ans=max(ans,a[i]*(r[i]-l[i]));
28         printf("Case %d: %d\n",TT,ans);
29     }
30     return 0;
31 }

法二：奇奇怪怪的方法，類似鏈表/kmp的預處理

left[i]和right[i]分別表示能擴展到的最左/右側的高度小於等於它的長條的編號。看起來可能很慢，但是實際上均攤複雜度O(n)。

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 int T,n,ans;
 5 int a[30100],left[30100],right[30100];
 6 int main()
 7 {
 8     int TT,i;
 9     scanf("%d",&T);
10     for(TT=1;TT<=T;TT++)
11     {
12         ans=0;
13         scanf("%d",&n);
14         for(i=1;i<=n;i++)
15             scanf("%d",&a[i]);
16         for(i=1;i<=n;i++)
17         {
18             left[i]=i;
19             while(left[i]>1&&a[left[i]-1]>=a[i])    left[i]=left[left[i]-1];
20         }
21         for(i=n;i>=1;i--)
22         {
23             right[i]=i;
24             while(right[i]<n&&a[right[i]+1]>=a[i])    right[i]=right[right[i]+1];
25         }
26         for(i=1;i<=n;i++)
27             ans=max(ans,a[i]*(right[i]-left[i]+1));
28         printf("Case %d: %d\n",TT,ans);
29     }
30 }