leetcode 85. Maximal Rectangle 最大子矩阵 + DP + 转换为最大直方图

朱雀 2022-06-08 02:26 152阅读 0赞

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.

这道题可以利用上一道题的解法，把一个求解子矩阵的问题分解为最大直方图问题。

要和[leetcode 84. Largest Rectangle in Histogram][] 放到一起学习。

代码如下：

import java.util.Stack;
    
    /*
     * 假设把矩阵沿着某一行分开，然后把分开的行作为底面，将自底面往上的矩阵看成一个直方图（histogram）。
     * 直方图的中每个项的高度就是从底面行开始往上1的数量。根据Largest Rectangle in Histogram就可以求出
     * 当前行作为矩阵下边缘的一个最大矩阵。接下来如果对每一行都做一次Largest Rectangle in Histogram，
     * 从其中选出最大的矩阵，那么它就是整个矩阵中面积最大的子矩阵。
     * 
     * 如何计算某一行为底面时直方图的高度呢？如果重新计算，那么每次需要的计算数量就是当前行数乘以列数。
     * 然而会发现一些动态规划的踪迹，如果知道上一行直方图的高度，就只需要看新加进来的行（底面）上对应的列
     * 元素是不是0，如果是，则高度是0，否则则是上一行直方图的高度加1。利用历史信息，就可以在线行时间内
     * 完成对高度的更新。由于Largest Rectangle in Histogram的算法复杂度是O(n)。所以完成对一行为底边的
     * 矩阵求解复杂度是O(n+n)=O(n)。接下来对每一行都做一次，那么算法总时间复杂度是O(m*n)。
     * 
     * */
    public class Solution 
    {   
        public int maximalRectangle(char[][] mat)
        {
            if(mat==null || mat.length<=0)
                return 0;
    
            int[] height=new int[mat[0].length];
            int maxArea=-1;
            for(int i=0;i<mat.length;i++)
            {
                for(int j=0;j<mat[0].length;j++)
                    height[j] = (mat[i][j]=='0') ? 0 : height[j]+1;
                maxArea=Math.max(maxArea, largestRectangleArea(height));
            }
            return maxArea;
        }
    
        public int largestRectangleArea(int[] height) 
        {
            if(height==null || height.length<=0)
                return 0;
            int maxArea=0,i=0;
            Stack<Integer> stack=new Stack<>();
            while(i<height.length)
            {
                //要是可以保证升序序列就直接进栈
                if(stack.isEmpty() || height[stack.peek()] <= height[i])
                    stack.push(i++);
                else 
                {
                    /*
                     * 否者的话直接计算以height[pre]为高度的面积，为什么呢？
                     * 因为假如pre之前有比height[pre]要小的元素，那么pre早就出栈了，
                     * 所以可以计算以height[pre]为高度的面积，那么宽度是哪里呢？
                     * 首先起点是stack的top+1，因为height[pre]要比现在的top的height要大，
                     * 同时重点是i-1，因为height[pre]>height[i]
                     * */
                    int pre=stack.pop();
                    int width=stack.isEmpty()?(i-1)-0+1 : (i-1)-(stack.peek()+1)+1;
                    maxArea=Math.max(maxArea, width * height[pre]);
                }
            }
    
            //其实到了这里i就是height.length
            while(stack.isEmpty()==false)
            {
                int pre=stack.pop();
                int width=stack.isEmpty()?(height.length-1)-0+1 : (height.length-1)-(stack.peek()+1)+1;
                maxArea=Math.max(maxArea, width * height[pre]);
            }
            return maxArea;
        }
    }

下面是C++的做法，这个是借助上一道题的做法

代码如下：

#include <iostream>
    #include <vector>
    #include <algorithm>
    #include <stack>
    
    using namespace std;
    
    class Solution 
    {
    public:
    
        int maximalRectangle(vector<vector<char>>& mat) 
        {
            if (mat.size() <= 0)
                return 0;
    
            int maxArea = -1;
            vector<int> dp(mat[0].size(),0);
            for (int i = 0; i < mat.size(); i++)
            {
                for (int j = 0; j < mat[0].size();j++)
                    dp[j] =(mat[i][j] == '0') ? 0 : dp[j]+1;
    
                maxArea = max(maxArea, largestRectangleArea(dp));
            }
            return maxArea;
        }
    
        int largestRectangleArea(vector<int>& hei) 
        {
            if (hei.size() <= 0)
                return 0;
            stack<int> index;
            int i = 0, maxArea = -1;
            while (i < hei.size())
            {
                if (index.empty() || hei[i] >= hei[index.top()])
                    index.push(i++);
                else
                {
                    int pre = index.top();
                    index.pop();
                    int width = index.empty() ? (i - 1) - 0 + 1 : (i - 1) - (index.top()+1) + 1;
                    maxArea = max(maxArea, width*hei[pre]);
                }
            }
    
            while (index.empty() == false)
            {
                int pre = index.top();
                index.pop();
                int width = index.empty() ? (hei.size() - 1) - 0 + 1 : (hei.size() - 1) - (index.top() + 1) + 1;
                maxArea = max(maxArea, width*hei[pre]);
            }
            return maxArea;
        }
    };

[leetcode 84. Largest Rectangle in Histogram]: http://blog.csdn.net/jackzhang_123/article/details/77942100