潮湿的天气和人的心理一样，散发出懒洋洋的热空气。懒的写东西，帖一篇Love_Shsean的文。
我们设柱型图的元素高度为h [ ]，那么我们要求的就是max { h [i] * (Right [i] - Left [i] + 1) }，其中Left [i]分别是以h [i]为中心，向左拓展使得h [j]~ h [i] <= h [i]的最大j，Right [i]也有类似的定义。
由此，我们来看一个子问题：已知数组h, 如何求Left [ ]。
算法1、枚举，O (N ^ 2)。
算法2、线段树，O (N Log N)。
算法3、用已经计算出的结果来加速当前的计算。
显然有这样的结论，如果当前计算的i (i > 0)，h [i] > h [i - 1]，显然Left [i] = i，否则我们要比较h [i - 2] 和 h [i]，那么如果我们已知了Left [ i - 1]，能不能用Left [i - 1]的结果来省去一些不必要的比较呢？
h [i] <= h [i - 1], h [i - 1] <= h [ Left [ i - 1] ] ，于是我们只要从Left [i - 1] - 1开始和h [i]比较就行了，省去了中间不必要的比较，同样的道理，我们可以一直迭代的来比较。代码只有两行：
for (i = 0; i < N; i ++)
for (Left [i] = i; Left [i] && h [Left [i] - 1] >= h [i]; Left [i] = Left [Left [i] - 1]);
极为简洁，O (N * Log*N) 已经很接近于O (N)了。
算法4、
在看算法4之前，我们先来看Zoj 1985的官方解法。
Linear search using a stack of incomplete subproblems
We process the elements in left-to-right order and maintain a stack of information about started but yet unfinished subhistograms. Whenever a new element arrives it is subjected to the following rules. If the stack is empty we open a new subproblem by pushing the element onto the stack. Otherwise we compare it to the element on top of the stack. If the new one is greater we again push it. If the new one is equal we skip it. In all these cases, we continue with the next new element.
If the new one is less, we finish the topmost subproblem by updating the maximum area w.r.t. the element at the top of the stack. Then, we discard the element at the top, and repeat the procedure keeping the current new element. This way, all subproblems are finished until the stack becomes empty, or its top element is less than or equal to the new element, leading to the actions described above. If all elements have been processed, and the stack is not yet empty, we finish the remaining subproblems by updating the maximum area w.r.t. to the elements at the top.
For the update w.r.t. an element, we find the largest rectangle that includes that element. Observe that an update of the maximum area is carried out for all elements except for those skipped. If an element is skipped, however, it has the same largest rectangle as the element on top of the stack at that time that will be updated later.
The height of the largest rectangle is, of course, the value of the element. At the time of the update, we know how far the largest rectangle extends to the right of the element, because then, for the first time, a new element with smaller height arrived. The information, how far the largest rectangle extends to the left of the element, is available if we store it on the stack, too.
We therefore revise the procedure described above. If a new element is pushed immediately, either because the stack is empty or it is greater than the top element of the stack, the largest rectangle containing it extends to the left no farther than the current element. If it is pushed after several elements have been popped off the stack, because it is less than these elements, the largest rectangle containing it extends to the left as far as that of the most recently popped element.
Every element is pushed and popped at most once and in every step of the procedure at least one element is pushed or popped. Since the amount of work for the decisions and the update is constant, the complexity of the algorithm is O(n) by amortized analysis.
这个解法维护了一个栈，递归地以O (N)的时间计算出了结果。
看一下代码吧：