leetcode：1139. 最大的以 1 为边界的正方形

题目来源

• leetcode：1139. 最大的以 1 为边界的正方形

题目描述

class Solution {
    
public:
    int largest1BorderedSquare(vector<vector<int>>& grid) {
    

    }
};

举个例子：可以肉眼看出一个满足条件的数组边长为 33 ，同时也是最大边长。

vector<vector<int>> grid ={
     {
    0, 1, 0, 1, 1},
							{
    1, 1, 1, 1, 1},
							{
    1, 1, 0, 1, 1},
							{
    1, 1, 1, 1, 0},
							{
    0, 1, 1, 1, 1},
							{
    1, 1, 1, 0, 1},
							{
    0, 1, 1, 1, 1},
							{
    1, 1, 1, 0, 1}
};


std::vector<std::vector<int>> grid = {
    
            {
    1, 1, 1},
            {
    1, 0, 1},
            {
    1, 1, 1}
    };

题目解析

动态规划

class Solution {
    
public:
    // 运用动态规划的思想，建立一个三维数组来存储每个点的左侧和上方连续的1的个数
    int largest1BorderedSquare(vector<vector<int>>& grid) {
    
        if(grid.empty()){
    
            return 0;
        }
        int length = grid.size(); //矩阵的长
        int width = grid[0].size(); //矩阵的宽

        //用dp[i][j][0]来表示第i行第j列的 左边 连续的1的个数
        //用dp[i][j][1]来表示第i行第j列的 上面 连续的1的个数
        std::vector<std::vector<std::vector<int>>> dp(
                   length + 1, std::vector<std::vector<int>>(
                    width + 1, std::vector<int>(
                    2, 0
                                )
                        )
                );

        int maxLen = 0;
        for (int i = 1; i <= length; ++i) {
    
            for (int j = 1; j <= width; ++j) {
    
                if(grid[i - 1][j - 1] == 1){
      //因为上面的代码 i 和 j 都是从1开始，到m，n结束，可以理解为在矩形的左边和上边加了一层0，所以实际的dp[i][j][0]其实是grid[i-1][j-1]左边连续的1的个数（包括自身），这样做其实就是为了方便初始化，避免写太多的if-else，是一种很常见的技巧
                    dp[i][j][0] += dp[i][j - 1][0] + 1;
                    dp[i][j][1] += dp[i - 1][j][1] + 1;
                    
                    //尝试以第i行第j列(当前点)为右下角构成正方形
                    int len = std::min(dp[i][j][0], dp[i][j][1]); //最大可能长度
                    while (len > 0){
    
                        //判断这个可能的正方形右上角左侧是否有连续len个1 && 左下角的上方是否有连续len个1
                        if(dp[i - len + 1][j][0] >= len && dp[i][j - len + 1][1] >= len){
    
                            break;
                        }
                        len--;
                    }
                    maxLen = std::max(maxLen, len);
                }
            }
        }
        return maxLen * maxLen;
    }
};