最大正方形

/*
 * 思路：
 * 我们使用动态规划来解决这个问题。定义一个二维dp数组，其中dp[i][j]表示以(i, j)为右下角的正方形的最大边长。
 * 初始化时，矩阵的第一行和第一列的dp值等于矩阵的值。对于其他元素，如果矩阵值为'1'，
 * 则dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1，否则dp[i][j] = 0。
 * 最后，遍历dp数组，找到最大的边长，并计算面积。
 * 此处使用Java Stream API来简化代码。
 */
import java.util.Arrays;
 
public class SolutionStream {
    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[] dp = new int[cols + 1];
        int maxSide = 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], dp[j]), prev) + 1;
                    maxSide = Math.max(maxSide, dp[j]);
                } else {
                    dp[j] = 0;
                }
                prev = temp;
            }
        }
        return maxSide * maxSide;
    }
}