221. 最大正方形

在一个由 ‘0’ 和 ‘1’ 组成的二维矩阵内，找到只包含 ‘1’ 的最大正方形，并返回其面积。
示例 1：

输入：matrix = [[“1”,“0”,“1”,“0”,“0”],[“1”,“0”,“1”,“1”,“1”],[“1”,“1”,“1”,“1”,“1”],[“1”,“0”,“0”,“1”,“0”]]
输出：4

示例 2：

输入：matrix = [[“0”,“1”],[“1”,“0”]]
输出：1

示例 3：

输入：matrix = [[“0”]]
输出：0

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 300
matrix[i][j] 为 ‘0’ 或 ‘1’

1.c++

/*
 *  date:   2022-06-04
 *  city:   hangzhou 
 *  author: zhangyb
 */

#include <vector>
#include <iostream>

class Solution
{
    
public:
    bool containCharInRow(int s,int e,int x,const std::vector<std::vector<char>>& matrix,const char character)
    {
    
        for (int i = s;i <= e;++i)
        {
    
            if (matrix[x][i] == character)
            {
    
                return true;
            }
        }
        return false;
    }

    bool containCharInCol(int s,int e,int y,const std::vector<std::vector<char>>& matrix,const char character)
    {
    
        for (int i = s;i <= e;++i)
        {
    
            if (matrix[i][y] == character)
            {
    
                return true;
            }
        }
        return false;
    }

    void getMaxArea(const int left,const int right,int x,int y,int &maxArea,const std::vector<std::vector<char>>& matrix)
    {
    
        if (x >= matrix.size() || y >= matrix[0].size() || matrix[x][y] == '0')
        {
    
            return;
        }

        if (containCharInRow(right,y,x,matrix,'0') || containCharInCol(left,x,y,matrix,'0'))
        {
    
            return;
        }

        maxArea += 2*(x - left) + 1;
        return getMaxArea(left,right,x+1,y+1,maxArea,matrix);
    }
    
    int maximalSquare(std::vector<std::vector<char>>& matrix) 
    {
    
        int maxArea = 0;
        int m = matrix.size();
        if (m < 1)
        {
    
            return maxArea;
        }
        
        int n = matrix[0].size();
        bool hasOne = 0;
        bool alreadyMax = 0;

        for (int i = 0; i < m;++i)
        {
    
            for (int j = 0; j < n;++j)
            {
    
                if (matrix[i][j] == '1')
                {
    
                    hasOne = 1;
                }
                else 
                {
    
                    continue;
                }
                
                if (i == m - 1 || j == n - 1)
                {
    
                    continue;
                }

                if (maxArea >= (m-i)*(n-j))//剪枝:当剩下的待计算的矩形的即使全为1的面积也小于当前已经得到的最大面积，那么就不用在计算了。
                {
    
                    alreadyMax = 1;
                    break;
                }

                int tmpArea = 1;                
                getMaxArea(i,j,i+1,j+1,tmpArea,matrix);
                maxArea = (maxArea < tmpArea)?tmpArea:maxArea;
            }

            if (alreadyMax == 1)
            {
    
                break;
            }
        }
        std::cout << "maxArea: " << maxArea << " hasOne: " << hasOne << std::endl;
        if (maxArea == 0)
        {
    
            return hasOne?1:0;
        }

        return maxArea;
    }
};

int main()
{
    
      Solution slu;
      std::vector<std::vector<char>> matrix = /*
                                               {
    {'1','0','1','0','0'},
                                               {'1','0','1','1','1'},
                                               {'1','1','1','1','1'},
                                               {'1','0','0','1','0'}};
                                              */
                                             {
    {
    '0','1'}};
      std::cout << slu.maximalSquare(matrix) << std::endl;
}

2.思路讲解

题目要从一个M x N的矩形中寻找由1组成的面积最大的正方型。

图1:

如上图，一眼看上去，就有很多符合条件的正方形，我们以对角坐标来表示一个符合条件的正方形。
比如[（0,0）～（1,1）]表示的面积为4的正方形、[（1,2）～（3,4）]表示的面积为6的正方形.

从这两个正方形我们可以得到这样的思路，一个面积大于1的正方型，比如[（1,2）～（3,4）],其内部的 [(1,2)_{(1,2)],[(1,2)}(2,3)]也均是正方形，也即是若要在题目所给的m*n的矩形中寻找一个最大的正方形，那么我们可以先找到第一个最直观的正方形（也就是某个坐标（x,y),满足matrix[x][y] == 1的坐标点），此时最大面积 maxArea = 1，然后沿着其对角线增大的正方形，并判断该正方形是否是全为1的，如果全为1,满足要求，更新最大面积 maxArea = 4。从而在遍历所有的点后一定能找到满足要求的矩形。

1. 算法过程

在找到第1个全为1的正方形的基础上，探索第2个正方形，满足要求.

在第2个全为1的正方形的基础上，探索第3个正方形，不满足要求.

从而可以得到以(0,0)为左上顶点的满足要求的正方形的最大面积为4.

以上步骤就是算法的描述，已经能够实现题目的要求，找到全为1的最大面积的矩形。

2. 剪枝优化

以下为一个优化点，如果没有优化点，是不能通过最后的case的。

依旧使用图1来说明，经过上面的步骤，我们可能得到的全为1的正方形的面积为:{1,4,9}

从本图来看，我们是先找到1,再找到4,再找到9,那如果我们先找到9,我们还有必要找4吗？

显然是没有这个必要的，所以我们当开始计算某个点(x,y)的满足要求的最大矩形面积前，我们应该先判断假如以(x,y)为左顶点的最大正方形，假设其全为1构成，并得到其面积 area_a,如果这个最大的假设的正方形的面积，已经小于前面求出来的最大矩形面积了，那我们就没有必要进行后续的面积的计算了。这就是剪枝优化。通过这个剪枝，能优化我们的程序时间复杂度。