欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-04-22 08:23:19
...

84Largest 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.

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

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

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

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;
    }
};

85Maximal 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;
        
    }
};