LeetCode: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. 本文地址

分析：最暴力的方法就是枚举所有区间的最大矩形值，然后选择最大的。可以通过分别枚举区间右边界和区间左边界，时间复杂度O(n^2)这样做大数据会超时。枚举的过程中可以优化一下：可以很容易理解，如果height[i+1] > height[i] 那么区间[k…i]内的最大矩形肯定不会超过区间[k…i+1]内的最大矩形，比如上例中的区间[0…3]内的矩形要大于[0…2]内的矩形，因为height[3] > height[2]。因此我们在枚举区间右边界时，只选择那些height上升区间的最大值处作为右边界（比如例子中的2 、6 、3）。优化后可以通过leetcode的大数据，虽然做了优化，但是时间复杂度还是O(n^2)，代码如下：

class Solution {
public:
    int largestRectangleArea(vector &height) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        int len = height.size(),res = 0;
        int rBorder = 0; //每次选择递增序列的最大值作为右边界
        while(rBorder < len)
        {
            if(rBorder + 1 < len && height[rBorder+1] >= height[rBorder])rBorder++;
            else
            {//找到了右边界
                int minVal = height[rBorder];
                //枚举左边界
                for(int lBorder = rBorder; lBorder >= 0; lBorder--)
                {
                    if(minVal > height[lBorder])
                        minVal = height[lBorder];
                    int tmpArea = minVal * (rBorder - lBorder + 1);
                    if(res < tmpArea)res = tmpArea;
                }
                rBorder++;
            }
        }
        return res;
    }
};

网上找到了一种O(n)的解法，非常巧妙，通过栈来维护height数组中递增的索引，具体可以参考这篇博客，这里只贴上代码：

class Solution {
public:
    int largestRectangleArea(vector<int> &height) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        height.push_back(0);//数组末尾插入dummy元素0
        int len = height.size(),res = 0;
        stack<int> S;//注意栈内保存的是数组height的下标索引
        for (int i = 0; i < len; i++) 
        {
             if (S.empty() || height[i] > height[S.top()]) S.push(i);
             else 
             {
                 int tmp = S.top();
                 S.pop();
                 res = max(res, height[tmp] * (S.empty() ? i : i-S.top()-1));
                 i--;
             }
        }
        height.pop_back();//删除dummy
        return res;
    }
};