LeetCode笔记（9）Largest Rectangle in Histogram

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 height = [2,1,5,6,2,3],
return 10.

这是Leetcode上一道很经典的题目，尝试很多次都没有清晰的头绪。与同属于Sequence类问题的trapped water等问题相比，这一题要更复杂，而且思路完全不同。

拿到手第一感觉有O(n^3)的暴力解法：方法一，对任意范围(l, r)找最小值，计算面积。

改进：方法二，固定一边l，然后从左到右scan寻找最小值，计算面积。复杂度O(n^2)。 与方法一相比优势在于：寻找最小值时同一起点的各个范围最小值相关，可以借用。使得最小值查找从O(n)变为O(1)

从leetcode各个题目的经验来看，这题绝不会这么简单，对于一个sequence的题目，极有可能的是会有O(n)的解法。

借鉴sequence的经验，使用双指针，从两头开始往中间扫，但是中间的最小值不知道没法计算两个指针之间的面积。试着用两个指针l，r从头开始走，但是找不出合理的走法。

杯具地没有想出来。。。。

于是从网上找到了这题的解法，看代码都花了很久才弄懂。具体思路如下：

方法三，这题的问题是找最大面积的长方形。长方形的底边是坐标轴，左边右边和顶边是不确定的。两个指针从两边往中间挪的思路或者两个指针从头开始走都是固定两边来寻找顶边。而下面的解法却是固定长方形的右边，再固定顶边，最后寻找左边。

对于一个i，如果height[i-1] <= height[i],那么以任意以i-1为右边的长方形必然可以扩展到第i列来增大面积，所以不是局部极大值，不用计算面积。

如果height[i-1] > height[i]，就需要计算以i-1为右边的极大长方形面积。（因为大于height[i]部分的面积在之后的计算中不会再使用，如果不计算则漏掉一部分情况）。

对于任意i而言，其之前部分的面积都是被“修剪”过的，参见这里

总体来说，思路就是通过一个stack来维护之前的histogram，只标记每个当前位置可用高度最早的可达位置。可用/可达的要求是：对从j到i-1之间所有k均满足：h[k] >= h[j]，且h[j] <= h[i-1]。每当有一部分面积会被“修剪”时，计算包含这部分面积的所有可能性。

代码如下：

    int largestRectangleArea(vector<int> &height) {
        int maxR = 0;
        height.push_back(-1);
        vector<int> left;
        for (int i=0; i<height.size(); i++)
        {
            while (!left.empty() && height[left.back()] > height[i])
            {
                int h = height[left.back()];
                left.pop_back();
                int l = left.empty() ? -1 : left.back();
                maxR = max(maxR, (i - l - 1) * h);
            }
            left.push_back(i);
        }
        return maxR;
    }

这一题总结下来，经验教训如下：

1. 思维不要太固化，套思路解题能做对一部分，但是没有长进，而且遇到变化就傻眼了，如果陷在原地出不来就会很浪费时间
2. 具体问题具体分析，如果从头开始仔细思考还是有机会想出来的。
3. 问题表述还需要大大加强，这题到现在都还不能很好地用中文表述出来，用英语就更不用说了。