Histogram LightOJ

题意：给出一个直方图，由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
",TT,ans);
29     }
30     return 0;
31 }

(由于题目的某些特性，即使单调栈在push时不把相同的pop出来也可以过。然而正确的单调栈一般都要把相同的也pop出来)

 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
",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
",TT,ans);
29     }
30 }

法三：一个区间由区间最小值控制。对于某一个区间，答案要么包含这个最小值，要么在最小值左侧区间取，要么在右侧区间取。因此预处理解决RMQ，然后分治解决。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 int T,TT,n;
 6 int minn[21][30100],a[30100];
 7 int query(int l,int r)
 8 {
 9     int k=0;
10     while((1<<(k+1))<=r-l+1)    ++k;
11     return a[minn[k][l]]>a[minn[k][r-(1<<k)+1]]?minn[k][r-(1<<k)+1]:minn[k][l];
12 }
13 int get(int l,int r)
14 {
15     if(l>r)    return 0;
16     if(l==r)
17         return a[l];
18     int pos=query(l,r);
19     return max(max(get(l,pos-1),get(pos+1,r)),a[pos]*(r-l+1));
20 }
21 int main()
22 {
23     int i,j;
24     scanf("%d",&T);
25     for(TT=1;TT<=T;TT++)
26     {
27         memset(minn,0,sizeof(minn));
28         memset(a,0,sizeof(a));
29         scanf("%d",&n);
30         for(i=1;i<=n;i++)
31             scanf("%d",&a[i]);
32         for(i=1;i<=n;i++)
33             minn[0][i]=i;
34         for(i=1;(1<<i)<=n;i++)
35             for(j=1;j<=n-(1<<i)+1;j++)
36                 minn[i][j]=a[minn[i-1][j]]>a[minn[i-1][j+(1<<(i-1))]]?minn[i-1][j+(1<<(i-1))]:minn[i-1][j];
37         printf("Case %d: %d
",TT,get(1,n));
38     }
39     return 0;
40 }