题解 | JAVA #最大正方形# [P0-T2]

mem[i][j]: 右下角坐标为(i,j)分正方形最大边长

if matrix[i][j] = 1: 
  mem[i][j] = 1+ MIN{
     mem[i-1][j], 
     mem[i-1][j-1], 
     mem[i][j-1]
  }

import java.util.*;

public class Solution {
    public int solve (char[][] matrix) {
      if (matrix.length == 0 || matrix[0].length == 0) return 0;
      
      // 把char换成int. 题目给char是真的烦
      int[][] mem = new int[matrix.length][matrix[0].length];
      for (int i = 0; i < matrix.length; i++) {
        for (int j = 0; j < matrix[0].length; j++) {
          mem[i][j] = (matrix[i][j] == '1') ? 1 : 0;
        }
      }
      
      int maxW = 0;
      // mem[0][j] and mem[i][0]都等于matrix[i][j], 不用再算
      for (int i = 1; i < matrix.length; i++) {
        for (int j = 1; j < matrix[0].length; j++) {
          if (mem[i][j] == 0) {
            continue;
          }
          mem[i][j] = 1 + Math.min(mem[i-1][j], 
                                   Math.min(mem[i][j-1], mem[i-1][j-1]));
          maxW = Math.max(maxW, mem[i][j]);
        }
      }
      
      return maxW * maxW;
    }
}