hdu1506 Largest Rectangle in a Histogram
对于每一个高度h[i]，搜索它能到达的最左，和最右，最大面积Smax = Max{ i | 面积Si = (最右 - 最左 + 1) *h[i] }
这样的时间复杂度为O（n^2）,必超时
举例 2,3,4,5
要判断2能到达最右的位置，不需要循环比较，只需要知道3能到达的最右是哪里，因为若3能到达的位置，2必然也能到达
1 #include<cstdio> 2 #include<iostream> 3 using namespace std; 4 5 int main() 6 { 7 int n; 8 while(scanf("%d", &n) && n) 9 { 10 long long h[100007]; 11 long long l[100007]; 12 long long r[100007]; 13 for(int i=1;i<=n;i++) 14 { 15 scanf("%lld", &h[i]); 16 l[i] = r[i] = i; 17 } 18 h[0] = h[n+1] = -1; 19 for(int i=1;i<=n;i++) 20 { 21 while(h[i] <= h[l[i]-1]) { 22 l[i] = l[l[i]-1]; 23 } 24 } 25 for(int i=n;i>=1;i--) 26 { 27 while(h[i] <= h[r[i]+1]) { 28 r[i] = r[r[i]+1]; 29 } 30 } 31 long long ans = 0; 32 for(int i=1;i<=n;i++) 33 { 34 ans = ans > (r[i]-l[i]+1)*h[i] ? ans : (r[i]-l[i]+1)*h[i]; 35 } 36 printf("%lld\n",ans); 37 } 38 }