题意：输入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。
Read full article from [POJ 2559] | Eurce's Blog
No comments:
Post a Comment