leetcode 221. Maximal Square | 221. 最大正方形（优化的暴力解法+动态规划解法）

蔚落 2022-10-07 12:57 187阅读 0赞

## 题目 ##

[https://leetcode.com/problems/maximal-square/][https_leetcode.com_problems_maximal-square]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

### 方法1：最暴力解 O((m\*n)^2) ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]

public class Solution { 
        public int maximalSquare(char[][] matrix) { 
            int rows = matrix.length, cols = rows > 0 ? matrix[0].length : 0;
            int maxsqlen = 0;
            for (int i = 0; i < rows; i++) { 
                for (int j = 0; j < cols; j++) { 
                    if (matrix[i][j] == '1') { 
                        int sqlen = 1;
                        boolean flag = true;
                        while (sqlen + i < rows && sqlen + j < cols && flag) { 
                            for (int k = j; k <= sqlen + j; k++) { 
                                if (matrix[i + sqlen][k] == '0') { 
                                    flag = false;
                                    break;
                                }
                            }
                            for (int k = i; k <= sqlen + i; k++) { 
                                if (matrix[k][j + sqlen] == '0') { 
                                    flag = false;
                                    break;
                                }
                            }
                            if (flag)
                                sqlen++;
                        }
                        if (maxsqlen < sqlen) { 
                            maxsqlen = sqlen;
                        }
                    }
                }
            }
            return maxsqlen * maxsqlen;
        }
    }

### 方法2：优化的暴力解法 O((m^2)\*n) ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 2]  
虽然时间复杂度相同，但本代码没有实现上述“只看4个点”，此处待改进…

class Solution { 
        public int maximalSquare(char[][] matrix) { 
            int[][] right = new int[matrix.length][matrix[0].length]; // 向右有多少个连续的1
            int[][] down = new int[matrix.length][matrix[0].length]; // 向下有多少个连续的1
            // right
            for (int i = matrix.length - 1; i >= 0; i--) { 
                int count = 0;
                for (int j = matrix[0].length - 1; j >= 0; j--) { 
                    if (matrix[i][j] == '0') count = 0;
                    else count++;
                    right[i][j] = count;
                }
            }
            // down
            for (int i = matrix[0].length - 1; i >= 0; i--) { 
                int count = 0;
                for (int j = matrix.length - 1; j >= 0; j--) { 
                    if (matrix[j][i] == '0') count = 0;
                    else count++;
                    down[j][i] = count;
                }
            }
            // check
            int area = 0;
            for (int i = 0; i < matrix.length; i++) { 
                for (int j = 0; j < matrix[0].length; j++) { 
                    if (right[i][j] > 0) { 
                        int square = right[i][j]; // 正方形最大边长
                        for (int k = 0; k < right[i][j]; k++) { 
                            square = Math.min(square, down[i][j + k]); // 最大边长要取min 因为受向下连续1个数的限制
                            area = Math.max(area, Math.min((k + 1) * (k + 1), square * square)); // 最大面积要取min 因为受到起点k的距离的限制
                        }
                    }
                }
            }
            return area;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]

附：左神算法配套代码，实现了上述“只看4个点”，供参考。

package chapter_8_arrayandmatrix;
    
    public class Problem_21_MaxOneBorderSize { 
    
    	public static void setBorderMap(int[][] m, int[][] right, int[][] down) { 
    		int r = m.length;
    		int c = m[0].length;
    		if (m[r - 1][c - 1] == 1) { 
    			right[r - 1][c - 1] = 1;
    			down[r - 1][c - 1] = 1;
    		}
    		for (int i = r - 2; i != -1; i--) { 
    			if (m[i][c - 1] == 1) { 
    				right[i][c - 1] = 1;
    				down[i][c - 1] = down[i + 1][c - 1] + 1;
    			}
    		}
    		for (int i = c - 2; i != -1; i--) { 
    			if (m[r - 1][i] == 1) { 
    				right[r - 1][i] = right[r - 1][i + 1] + 1;
    				down[r - 1][i] = 1;
    			}
    		}
    		for (int i = r - 2; i != -1; i--) { 
    			for (int j = c - 2; j != -1; j--) { 
    				if (m[i][j] == 1) { 
    					right[i][j] = right[i][j + 1] + 1;
    					down[i][j] = down[i + 1][j] + 1;
    				}
    			}
    		}
    	}
    
    	public static int getMaxSize(int[][] m) { 
    		int[][] right = new int[m.length][m[0].length];
    		int[][] down = new int[m.length][m[0].length];
    		setBorderMap(m, right, down);
    		for (int size = Math.min(m.length, m[0].length); size != 0; size--) { 
    			if (hasSizeOfBorder(size, right, down)) { 
    				return size;
    			}
    		}
    		return 0;
    	}
    
    	public static boolean hasSizeOfBorder(int size, int[][] right, int[][] down) { 
    		for (int i = 0; i != right.length - size + 1; i++) { 
    			for (int j = 0; j != right[0].length - size + 1; j++) { 
    				if (right[i][j] >= size && down[i][j] >= size
    						&& right[i + size - 1][j] >= size
    						&& down[i][j + size - 1] >= size) { 
    					return true;
    				}
    			}
    		}
    		return false;
    	}
    
    	public static int[][] generateRandom01Matrix(int rowSize, int colSize) { 
    		int[][] res = new int[rowSize][colSize];
    		for (int i = 0; i != rowSize; i++) { 
    			for (int j = 0; j != colSize; j++) { 
    				res[i][j] = (int) (Math.random() * 2);
    			}
    		}
    		return res;
    	}
    
    	public static void printMatrix(int[][] matrix) { 
    		for (int i = 0; i != matrix.length; i++) { 
    			for (int j = 0; j != matrix[0].length; j++) { 
    				System.out.print(matrix[i][j] + " ");
    			}
    			System.out.println();
    		}
    	}
    
    	public static void main(String[] args) { 
    		int[][] matrix = generateRandom01Matrix(7, 8);
    		printMatrix(matrix);
    		System.out.println(getMaxSize(matrix));
    	}
    }

### 方法3：动态规划 ###

思路来源：leetcode 官方题解  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 5]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 6]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]

动态规划最重要的就是想清楚 d\[i,j\] 代表着什么，这个太重要了。

这道题中的 d\[i, j\] 代表的是，以坐标点(i,j) 为右下角的最大正方形，如果说你的 d\[i,j\] 是想这个区域中最大的正方形，那可就麻烦太多了。

官方题解代码：

public class Solution { 
        public int maximalSquare(char[][] matrix) { 
            int rows = matrix.length, cols = rows > 0 ? matrix[0].length : 0;
            int[][] dp = new int[rows + 1][cols + 1];
            int maxsqlen = 0;
            for (int i = 1; i <= rows; i++) { 
                for (int j = 1; j <= cols; j++) { 
                    if (matrix[i-1][j-1] == '1'){ 
                        dp[i][j] = Math.min(Math.min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1;
                        maxsqlen = Math.max(maxsqlen, dp[i][j]);
                    }
                }
            }
            return maxsqlen * maxsqlen;
        }
    }

### 方法4：动态规划的优化解法 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 3]

public class Solution { 
        public int maximalSquare(char[][] matrix) { 
            int rows = matrix.length, cols = rows > 0 ? matrix[0].length : 0;
            int[] dp = new int[cols + 1];
            int maxsqlen = 0, prev = 0;
            for (int i = 1; i <= rows; i++) { 
                for (int j = 1; j <= cols; j++) { 
                    int temp = dp[j];
                    if (matrix[i - 1][j - 1] == '1') { 
                        dp[j] = Math.min(Math.min(dp[j - 1], prev), dp[j]) + 1;
                        maxsqlen = Math.max(maxsqlen, dp[j]);
                    } else { 
                        dp[j] = 0;
                    }
                    prev = temp;
                }
            }
            return maxsqlen * maxsqlen;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 7]

[https_leetcode.com_problems_maximal-square]: https://leetcode.com/problems/maximal-square/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20221005/92556972d14e4650a3695c3e5f882709.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]: /images/20221005/f7ffdd8dcd6b4f119de8fc5f5bb0b485.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 1]: /images/20221005/626a4fe14eb0497999e49a7f5d51cec5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 2]: /images/20221005/d1b61da1f9394d6fba95bbfb7a5adca4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20221005/aefe2dc58c1446e5bc54af54c75efb8e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 3]: /images/20221005/7ff44af1b2f2460dabc266f155a905d2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 4]: /images/20221005/1a447b1f11624c5ab22bcc9ce5f627b1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 5]: /images/20221005/7b35436fa4d34b45a680304ed442c3c2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 6]: /images/20221005/8acc5601bef247b48ed1fa19941f1599.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]: /images/20221005/e8c70cc9374345d6ab6ca0859556f3fc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 3]: /images/20221005/9357b279b3ce4a888458d97c2995d141.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 7]: /images/20221005/53c1471674a44845b67aa6b2b0cb6aa0.png