Largest Rectangle in Histogram题解

一. 题目简述，这是LeetCode上的一道题，是求直方图最大面积，原题题干如下：

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)。

另外一种方法则是助教的思路，据说是利用栈来解决这个问题，不过我却想不到QAQ...于是我上网查了下，感觉这个方法相对巧妙，查到这个方法后一开始并没有理解，在纸上画了图又操作了一遍之后终于差不多搞明白了。这个方法的巧妙之处在于首先他确保了栈中元素的高度和位置都是递增的，同时他通过出栈这个方式同时做到了求矩形面积和保留该矩形最左侧的位置高度（这个高度也是这个矩形的最低高度）信息，减少了很多运算量，把时间复杂度变成了O(n)。这个方法的具体实现步骤如下（说的比较墨迹...）：

用两个栈分别储存当前矩形的高度和此时的矩形下标。从第一个位置开始遍历，若新的位置比栈顶高度高，则将新位置的高度和位置入栈；否则则一直出栈，直到遇到比新的位置高度更低的矩形为止，此时将新的位置高度入栈，再将最后一个出栈的矩形下标入栈，在这个过程中，每次有东西出栈时，就求一次矩形的面积，矩形面积的高度为即将出栈的矩形高度，宽度为当前遍历到的位置和栈顶矩形位置之间的矩形数量（包括两侧的矩形）。

遍历结束之后，栈里还有一些东西，再把栈里的东西依次出栈，每次出栈之前按上述方法求面积，在求到的一堆面积时找到最大的就是要求得面积了~

class Solution {
public:
    int largestRectangleArea(vector<int>& height) {
        if(height.size() == 0)  　　　　　　//对应空直方图的情况
            return 0;
        stack<int> tempheight;
        stack<int> temppos;
        tempheight.push(-1);　　　　　　　　
        temppos.push(-1);
        int area = 0;
        int maxArea = 0;
        for(int i = 0; i < height.size(); i++)
        {
            if(height[i] >= tempheight.top())     
            {
                tempheight.push(height[i]);
                temppos.push(i);
            }
            else
            {
                int tempPos = -1;
                while(height[i] <= tempheight.top())
                {
                    tempPos = temppos.top();
                    area = tempheight.top() * ( i - temppos.top());
                    if(area > maxArea)
                        maxArea = area;
                    tempheight.pop();
                    temppos.pop();
                }
                tempheight.push(height[i]);
                temppos.push(tempPos);
            }
        }
        while(tempheight.top() != -1)
        {
            area = tempheight.top() * ( height.size() - temppos.top());
            if(area > maxArea)
                maxArea = area;
            tempheight.pop();
            temppos.pop();
        }
        return maxArea;
    }
};