描述 Description

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,
Given heights = [2,1,5,6,2,3],
return 10.

[Largest Rectangle in Histogram]

分析 Analysis

在直方图中，一个长方形由其左边界和右边界决定，其最大可能的高度由两者中的最小者决定。

记 R(i,j) 为由第 i 个直方柱为左边界，第 j 个直方柱确定的面积最大的长方形。如果 R(i,j) 的面积最大，那么，第 i 个直方柱比第 i-1 个直方柱（如果存在的话）要高，而 第 j 个直方柱的高度也比第 j+1 个的要高，否则，由 R(i,j+1) 或 R(i-1,j) 的面积比 R(i,j) 还要大，这违背了 R(i,j) 的最优性。

根据这个观察，我们从第1个直方柱开始，寻找第一个 i, 使得直方柱 i 的高度比 i+1 的大，则 i 是一个可能的右边界，而 i 之前的每一根(高度上升的，可以通过一个上升栈保存)直方柱都有可能是左边界（因为 i 是第一个比 i + 1 高的直方柱，所以，在 i 之前的是一个上升的直方柱序列，每一根都比前一根要高）。这时，我们计算前面所有可能的长方形的面积（当然出栈的高度要比右边界i下一个i+1要高，否则肯定不是最优的，因为还可以加上i+1那个面积，所以出栈是出到刚好比i+1高的那个），并跟当前已知的最大值进行比较，并更新当前已知的最大值。然后，我们继续向前搜索，将当前栈还要高的直方柱都加到栈中，并找到第二个这样的 i 使得直方柱 i 的高度比 i+1 的大。重复这个过程，直到最后一根直方柱。这样，我们已经遍历了所有可能是最优解的长方形，并取了其中的最大值。

所以此算法的原理就是找到所有可能的右边界，然后对每个可能的右边界找到其可能的左边界。这样就找全了所有的情况。

解决步骤为

1) Create an empty stack.

2) Start from first bar, and do following for every bar ‘hist[i]’ where ‘i’ varies from 0 to n-1.
……a) If stack is empty or hist[i] is higher than the bar at top of stack, then push ‘i’ to stack.
……b) If this bar is smaller than the top of stack, then keep removing the top of stack while top of the stack is greater. Let the removed bar be hist[tp]. Calculate area of rectangle with hist[tp] as smallest bar. For hist[tp], the ‘left index’ is previous (previous to tp) item in stack and ‘right index’ is ‘i’ (current index).

3) If the stack is not empty, then one by one remove all bars from stack and do step 2.b for every removed bar.

[Largest Rectangular Area in a Histogram | Set 2]

复杂度分析

至于时间复杂度，似乎还不太明显。对每个直方柱，我们通过跟后一个进行比较就知道其是否为一个可能的右边界。如果是，则需要对前面的一个上升序列的每个直方住计算其和 i 确定的最大长方形的面积，这个上升序列最差情况下似乎有 O(n) 长，但是注意到，每个可能的左边界只会被计算一次（我们使用一个栈来保存前面的上升直方柱序列，当遇到一个可能的右边界时，把这些可能的左边界都弹出来，并计算其和右边界确定的长方形面积。显然，每个可能的左边界只会放栈一次），因此，总的时间复杂度为 O(n)。

代码 Code

  class Solution {
    public:
        int largestRectangleArea(vector<int> &height) {

            int ret = 0;
            height.push_back(0);
            vector<int> index;

            for(int i = 0; i < height.size(); i++)
            {
                while(index.size() > 0 && height[index.back()] >= height[i])
                {
                    int h = height[index.back()];
                    index.pop_back();

                    int sidx = index.size() > 0 ? index.back() : -1;
                    if(h * (i-sidx-1) > ret)
                        ret = h * (i-sidx-1);
                }
                index.push_back(i);
            }

            return ret;
        }
    };