Q221 最大正方形

佚名 6年前 (2019-04-23) 随笔 1208人围观抢沙发百度已收录

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

示例:

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

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;
    }
}