【Leetcode】85. Maximal Rectangle（求最大矩形）（动态规划）

一时失言乱红尘 2022-02-23 09:50 279阅读 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.

**Example:**

Input:
    [
      ["1","0","1","0","0"],
      ["1","0","1","1","1"],
      ["1","1","1","1","1"],
      ["1","0","0","1","0"]
    ]
    Output: 6

题目大意：

给出一个二维矩阵，求出其中全为‘1’的最大矩形的面积。

解题思路：

本题紧接第84题。

84题题解：[https://blog.csdn.net/qq\_29600137/article/details/89069243][https_blog.csdn.net_qq_29600137_article_details_89069243]

84题是前提假设了他们的高度在一个水平线上，求出最大矩形。同样本题也是求出最大矩阵，其相互之间一定有联系。我们可以将这个二维矩阵通过一层一层的依次查看之后我们就可以看出其实最大矩阵出现在第一层到第三层中，其地位位于同一个水平线上，所以我们可以一次遍历每一层，传入前初始化好每一层该列底部连续1的个数。

class Solution {
    private:
    int largestRectangleArea(vector<int>& heights) {
            int n = heights.size();
            vector<int> l(n,0),r(n,n);
            for(int i = 1;i<n;i++){
                int p = i-1;
                while(p>=0&&heights[p]>=heights[i]){     
                    p = l[p] - 1;
                }
                l[i] = p + 1;
            }
            for(int i = n-2;i>=0;i--){
                int p = i+1;
                while(p<n&&heights[p]>=heights[i]){
                    p=r[p];
                }
                r[i] = p;
            }
            int ans = 0;
            for(int i = 0;i<n;i++){
                ans = max(ans, (r[i]-l[i])*heights[i]);
            }
            
            return ans;
        }
    public:
        int maximalRectangle(vector<vector<char>>& matrix) {
            if(matrix.size()==0) return 0;
            int maxans = 0;
            int n = matrix.size(), m = matrix[0].size();
            vector<vector<int>> matrix_num(n,vector<int>(m,0));
            for(int i=0;i<n;i++){
                for(int j=0;j<m;j++){
                    matrix_num[i][j] = matrix[i][j] - '0';
                }
            }
            for(int i = 0;i<n;i++){
                if(i==0){
                    maxans = max(maxans,largestRectangleArea(matrix_num[0]));
                }
                else{
                    for(int j = 0;j<m;j++){
                        if(matrix_num[i][j] == 1) matrix_num[i][j] += matrix_num[i-1][j];
                    }
                    maxans = max(maxans, largestRectangleArea(matrix_num[i]));
                }
            }
            return maxans;
        }
    };

[https_blog.csdn.net_qq_29600137_article_details_89069243]: https://blog.csdn.net/qq_29600137/article/details/89069243