Largest Rectangle in a Histogram
扫描栈 + 二分
题意：输入n(<=100,000)，然后是n个整数值h[i](<=10^9)，每个值按顺序描述了一个宽为1高为h[i]的矩形，矩形间是无缝相邻的，求该柱形图内边与坐标轴平行的矩形的最大面积。 拿到手之后第一想法是二分面积+RMQ判断，结果发现行不通…… 看了discuss可以用栈水过，就大概写了一下。 基本思想是，对于位置i，分别找其左边和右边高度不小于h[i]的最长宽度wl[i]和wr[i]，那么h[i]对应的最大矩形面积就是h[i]*(wl[i]+wr[i]-1)。分别求出对于所有n个位置的最大矩形面积就能得到答案了。 具体实现方面，计算wl[i]和wr[i]时，需要维护一个栈stk，记录扫描到i时，到i为止非递减的h[i]序列。例如对于“7 2 1 4 5 1 3 3”的样例，当i=3即h[i]=5时，栈里面分别是1、4、5，同时也需要记录这些值对应的位置。有了该栈，就可以找到刚好不小于h[i]的值stk[l]以及对应的位置si[l]，从而算出wl[i]、wr[i]。其中，由于栈有序，可以二分查找，那么计算wl[i]和wr[i]的时间复杂度便是O(lgn)，从而总体复杂度就是O(nlgn)的。 还有一些细节：例如总是将栈顶置为最大值，这样二分查找如果失败将返回栈顶位置，方便了处理；另外结果需要用到long long。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 |
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define ll long long int n,h[100000],wl[100000],wr[100000]; int stk[100001],si[100001],sl; ll ans; int bs(int l,int h,int e) { int m; while(l<h) { m=l+h>>1; if(stk[m]>=e) h=m; else l=m+1; } return l; } void init() { int i,j,k,l; ans=0; for(i=0;i<n;i++) scanf("%d",h+i); sl=0; stk[sl]=0x7fffffff; for(i=0;i<n;i++) { l=bs(0,sl,h[i]); if(l==sl) { wl[i]=1; stk[sl]=h[i]; si[sl++]=i; stk[sl]=0x7fffffff; } else { wl[i]=i-si[l]+wl[si[l]]; sl=l; stk[sl]=h[i]; si[sl++]=i; stk[sl]=0x7fffffff; } } sl=0; stk[sl]=0x7fffffff; for(i=n-1;i>-1;i--) { l=bs(0,sl,h[i]); if(l==sl) { wr[i]=1; stk[sl]=h[i]; si[sl++]=i; stk[sl]=0x7fffffff; } else { wr[i]=si[l]-i+wr[si[l]]; sl=l; stk[sl]=h[i]; si[sl++]=i; stk[sl]=0x7fffffff; } } } void solve() { ll i,j; for(i=0;i<n;i++) { j=wl[i]+wr[i]-1; ans=max(ans,j*h[i]); } printf("%lld\n",ans); } int main() { while(~scanf("%d",&n)&&n) { init(); solve(); } return 0; } |
还有一道差不多的：Feel Good
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 |
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define ll long long int n,h[100000],wl[100000],wr[100000]; ll shl[100000],shr[100000]; int stk[100001],si[100001],sl; ll ans,ansl,ansr; int bs(int l,int h,int e) { int m; while(l<h) { m=l+h>>1; if(stk[m]>=e) h=m; else l=m+1; } return l; } void init() { int i,j,k,l; ans=-1; for(i=0;i<n;i++) scanf("%d",h+i); shl[0]=h[0]; for(i=1;i<n;i++) shl[i]=shl[i-1]+h[i]; shr[n-1]=h[n-1]; for(i=n-2;i>-1;i--) shr[i]=shr[i+1]+h[i]; sl=0; stk[sl]=0x7fffffff; for(i=0;i<n;i++) { l=bs(0,sl,h[i]); if(l==sl) { wl[i]=1; stk[sl]=h[i]; si[sl++]=i; stk[sl]=0x7fffffff; } else { wl[i]=i-si[l]+wl[si[l]]; sl=l; stk[sl]=h[i]; si[sl++]=i; stk[sl]=0x7fffffff; } } sl=0; stk[sl]=0x7fffffff; for(i=n-1;i>-1;i--) { l=bs(0,sl,h[i]); if(l==sl) { wr[i]=1; stk[sl]=h[i]; si[sl++]=i; stk[sl]=0x7fffffff; } else { wr[i]=si[l]-i+wr[si[l]]; sl=l; stk[sl]=h[i]; si[sl++]=i; stk[sl]=0x7fffffff; } } } void solve() { ll i,ji,ki,j,k,l; for(i=0;i<n;i++) { ji=i-wl[i]+1; j=shl[i]-shl[ji]+h[ji]; ki=i+wr[i]-1; k=shr[i]-shr[ki]+h[ki]; l=h[i]*(j+k-h[i]); if(l>ans) { ans=l; ansl=ji+1; ansr=ki+1; } } printf("%lld\n%lld %lld\n",ans,ansl,ansr); } int main() { while(~scanf("%d",&n)) { init(); solve(); } return 0; } |