LeetCode Top 100 Liked Questions 221. Maximal Square (Java版; Medium)

welcome to my blog

LeetCode Top 100 Liked Questions 221. Maximal Square (Java版; Medium)

题目描述

Given a 2D binary matrix filled with 0's and 1's, find the largest square 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: 4

第一次做; 暴力法; 矩阵类型的题目要会暴力法!; 核心:每次扩张一个直角, 看注释

执行用时 :5 ms, 在所有 Java 提交中击败了99.20%的用户
内存消耗 :40.4 MB, 在所有 Java 提交中击败了95.65%的用户

/*
矩阵的题目, 暴力方法需要掌握, 最核心的就是要看懂下面这个矩阵, 这就是扩张方式!!!!!都次都扩张一个直角
12345
22345
33345
44445
55555
假设矩阵某一点是'1', 以该点作为正方形的左上角, 开始扩张, 一层一层地扩张, 就像上面写的一样, 同一个数字代表一层
*/
class Solution {
    public int maximalSquare(char[][] matrix) {
        if(matrix==null || matrix.length==0 || matrix[0].length==0)
            return 0;
        int rows = matrix.length, cols = matrix[0].length;
        int max = 0;
        for(int i=0; i<rows; i++){
            for(int j=0; j<cols; j++){
                if(matrix[i][j]=='1'){
                    int curr = expand(matrix, i, j);
                    max = Math.max(curr, max);
                }
            }
        }
        return max*max;
    }
    public int expand(char[][] matrix, int i, int j){
        //能进入这个函数, 说明matrix[i][j]=='1', 所以正方形的边长至少是1
        int len = 1;
        //a表示当前要探索的边长, 最因为a不合格跳出循环, 所以最大扩张长度是a-1, 令len=len+a-1即可
        int a = 1;
        //向右下方探索更大的正方形, 核心: 注意从哪一行向右探索, 看最上面注释的例子
        boolean flag = true;
        while(isValid(matrix, i+a, j) && isValid(matrix, i, j+a)){
            //从底下向右探索; 不满足条件要将flag置为false再break
            for(int m=j; m<=j+a ; m++){
                if(matrix[i+a][m] == '0'){
                    flag = false;
                    break;
                }

            }
            //从上面向下探索; 不满足条件要将flag置为false再break
            for(int m=i; m<=i+a && flag; m++){
                if(matrix[m][j+a]=='0'){
                    flag = false;
                    break;
                }                    
            }
            if(flag==false)
                break;
            //update
            a++;
        }
        return len+a-1;
    }
    public boolean isValid(char[][] matrix, int i, int j){
        return i>=0 && i<matrix.length && j>=0 && j<matrix[0].length;
    }
}

第一次做; 动态规划, 搞明白扩张方式后再理解动态规划都不那么难了, 所以说暴力法是非常重要的, 先学会走再学会跑;回想LeetCode84和85题