221. Maximal Square.md

Solution1

class Solution {
    public int maximalSquare(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        int[] heights = new int[matrix[0].length + 1];
        int max = 0;
        
        for (int i = 0; i < matrix.length; i++) {
            Stack<Integer> stack = new Stack<>();
            for (int j = 0; j < heights.length; j++) {
                if (j < heights.length - 1) {
                    heights[j] = matrix[i][j] == '1' ? heights[j] + 1 : 0;
                }
                if (stack.empty() || heights[j] >= heights[stack.peek()]) {
                    stack.push(j);
                }
                else {
                    while (!stack.empty() && heights[stack.peek()] > heights[j]) {
                        int top = stack.pop();
                        int l = stack.empty() ? j : (j - stack.peek() - 1);
                        int w = heights[top];
                        int a = Math.min(l, w);
                        max = Math.max(max, a * a);
                    }
                    stack.push(j);
                }
            }
        }
        return max;
    }
}

note

• O(m * n) space O(n)
• The idea is similar to Maximal Rectangle using monotonic stack and cache array.
• Be careful that when calculating area, we take the smaller side to multiply to itself because we want area of square.