ZJU/ZOJ 1985 Largest Rectangle in a Histogram 解题报告

题目大意是给出n个柱形的高度，求其中最大的矩形面积。

用left[i]表示取第i个柱形达最大面积时最左端的柱形，right[i]表示取第i个柱形达最大面积时最右端的柱形。则可顺推出left[i]=left[left[i]-1](2<=i<=n,h[left[i]]>=h[i],left[i]>1),逆推出right[i]=right[right[i]+1](1<=i<=n-1,h[right[i]>=h[i],right[i]<n)。然后扫一遍根据left[i]和right[i]计算面积即可。

3005375 2008-07-25 22:48:33 Accepted 1985 FPC 00:00.23 1584K IwfWcf