Q221 最大正方形

在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。

示例:

输入:

1 0 1 0 0

1 0 1 1 1

1 1 1 1 1

1 0 0 1 0

输出: 4

class Solution {

    public int maximalSquare(char[][] matrix) {

        if (matrix == null || matrix.length == 0 || matrix[0].length == 0)

            return 0;

        int max = 0;

        int[] heights = new int[matrix[0].length];

        for (char[] line : matrix) {

            for (int i = 0; i < line.length; i++)

                heights[i] = line[i] == '0' ? 0 : heights[i] + 1;

            int temp = findMaxSize(heights);

            max = max > temp ? max : temp;

        }

        return max;

    }

    private int findMaxSize(int[] heights) {

        Deque<Integer> stack = new LinkedList<>();

        int maxSize = 0;

        for (int i = 0; i < heights.length; i++) {

            while (!stack.isEmpty() && heights[stack.peek()] > heights[i]) {

                int t = stack.pop();

                int left = stack.isEmpty() ? - 1 : stack.peek();

                int right = i;

                int minLength = heights[t] < right - left - 1 ? heights[t] : right - left - 1;

                maxSize = maxSize > minLength * minLength ? maxSize : minLength * minLength;

            }

            stack.push(i);

        }

        while (!stack.isEmpty()) {

            int t = stack.pop();

            int left = stack.isEmpty() ? t - 1 : stack.peek();

            int right = heights.length - 1;

            int minLength = heights[t] < right - left ? heights[t] : right - left;

            maxSize = maxSize > minLength * minLength ? maxSize : minLength * minLength;

        }

        return maxSize;

    }

}