利用stack求柱状图的最大矩形面积

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

问题解析：

1. 本题的意思是：给定一个arr，在arr中找出面积最大的矩形。

2. 最简单的暴力求解是，相当于找出一个左边界和右边界，在计算两个边界之间高度最小的矩形面积。这种方法一定能够找出最大面积，但是时间复杂度是O(n^2)，不能AC。

3. 时间复杂度为O(n)的解法。设置一个辅助栈sta，从arr第0个数开始，当arr[i]大于等于sta.top()时，就压入栈，否则，说明sta.top()那个数的右边界已经找到，则弹出sta.top()，计算当前面积cur，并与最大面积max比较大小或替换。弹出top时，一直弹出到当前的top值小于或者等于arr[i]为止。并记录刚才弹出了几个top，就再次压入栈中几个arr[i]，最后压入当前的arr[i]。

代码如下：

class Solution {
public:
    // 利用堆栈来解决
    int largestRectangleArea(vector<int>& heights) 
    {
        if(heights.empty())
            return 0;
        stack<int>sta;
        int cur = 0, max = 0;
        int len = 0;
        int size = heights.size();
        for(int i=0; i<size; ++i)
        { 
            if(sta.empty() || sta.top() <= heights[i])
                sta.push(heights[i]);
            else
            {
                len = 0;
                while(!sta.empty() && sta.top() > heights[i])
                {
                    ++ len;
                    cur  = sta.top()*len;
                    if(cur > max)   max = cur;
                    sta.pop();
                }
                while(len)
                {
                    --len;
                    sta.push(heights[i]);
                }
                sta.push(heights[i]);
            }
        }
        while(!sta.empty())
        {
            ++ len;
            cur  = sta.top()*len;
            if(cur > max)   max = cur;
            sta.pop();
        }
        
        return max;
    }
};

85. Maximal Rectangle

问题描述：

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.

For example, given the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Return 6.

问题解析：

1. 此题是求矩阵中为1的最大的矩形元素个数。
2. 此题可以化为上题中求柱状图最大面积。从矩阵第0行开始，每一行可以看成是一个heights数组，本行j位置为1，如果上一行此列为1，则heights[j] = height[j]+1，然后求最大矩形面积，利用上题代码。

代码如下：

class Solution {
public:
    // 利用堆栈求最大的数字
    void largestRectangleArea(vector<int>& heights, int &max) 
    {
        if(heights.empty())
            return;
        stack<int>sta;
        int cur = 0;
        int len = 0;
        int size = heights.size();
        for(int i=0; i<size; ++i)
        { 
            if(sta.empty() || sta.top() <= heights[i])
                sta.push(heights[i]);
            else
            {
                len = 0;
                while(!sta.empty() && sta.top() > heights[i])
                {
                    ++ len;
                    cur  = sta.top()*len;
                    if(cur > max)   max = cur;
                    sta.pop();
                }
                while(len)
                {
                    --len;
                    sta.push(heights[i]);
                }
                sta.push(heights[i]);
            }
        }
        while(!sta.empty())
        {
            ++ len;
            cur  = sta.top()*len;
            if(cur > max)   max = cur;
            sta.pop();
        }
        
        return;
    }
    int maximalRectangle(vector<vector<char>>& matrix) 
    {
        int m=matrix.size(), n=0;
        if(m>0) n=matrix[0].size();
        int max = 0;
        vector<int> heights(n, 0);
        for(int i=0; i<m; ++i)
        {
            for(int j=0; j<n; ++j)
            {
                heights[j] = matrix[i][j]=='1'? heights[j]+1 : 0;
            }
            largestRectangleArea(heights, max);
        }
        return max;
        
    }
};