221. Maximal Square

问题

这个问题是说，找到一个m*n大小的matrix中面积最大的正方形区域，这个区域满足里面全是1。

解析

这个问题一开始想的就是从一个坐标开始，以他为右下角的区域的找到最大的正方形，然后一直找知道找到右下角最终结果。类似那种网格问题一样。

但是后面一直卡在如何确认在当前状态下一个一这个点为边的正方形是满足条件的（都为1）。

直到看了解析，求面积最大其实就是求边最大。那么问题就没有和整个matrix割裂了。状态的定义就成了以他为右下角的区域的找到最大的边即可。

状态转移公式对于当前点来说就来自于他的上面，左边，或者左上方对角线的最小值（因为对于不论哪个方向要都满足才可以所以找的是最小值）。

代码

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

Problem

This problem is to find the largest square area in a matrix of size m*n that satisfies all 1's in it.

Solution

The problem starts with the idea of finding the largest square in the area of the lower-right corner of the m*n matrix, and then looking for the final result in the lower-right corner. It is similar to the grid problem.

But later on, I was stuck on how to confirm that a square in the current state with this point as a side is satisfied (all 1).

Until I read the analysis, seeking the maximum area is actually seeking the maximum side. Then the problem is not cut off from the whole matrix. The definition of the state becomes to find the largest side of the area with him as the lower right corner can be.

The state transfer formula for the current point comes from the top, left, or top left diagonal of the minimum value (because for either direction to be satisfied to find the minimum value).

Code

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

10K's