My AC Java solution base on the idea of Maximal Rectangle


  • 0
    W

    The Code is almost same as the code of Maximal Rectangle

    public static int maximalSquare(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
        int area = 0, height = matrix.length, width = matrix[0].length;
        int A[][] = new int[height][width + 1];
        if (matrix != null) for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++)
                if (matrix[i][j] == '1') A[i][j] += ((i == 0 ? 0 : A[i - 1][j]) + 1);
                else A[i][j] = 0;
            area = Math.max(area, largestSquareArea(A[i]));
        }
        return area;
    }
    
    public static int largestSquareArea(int[] height) {
        LinkedList<Integer> stack = new LinkedList<Integer>();
        int max = 0, top = 0;
        boolean flag = true;
        for (int i = 0; i < height.length; i++)
            if (height[i] > 0 && (stack.isEmpty() || height[stack.peekLast()] <= height[i])) stack.addLast(i);
            else {
                if (!stack.isEmpty() && flag) {
                    top = stack.peekFirst();
                    flag = false;
                }
                while (!stack.isEmpty() && height[stack.peekLast()] > height[i]) {
                    int t = stack.pollLast();
                    max = Math.max(max, (int) Math.pow(
                            Math.min(height[t], (stack.isEmpty() ? i - top : i - stack.peekLast() - 1)), 2));//change from rectangle to square,done
                }
                if (height[i] > 0) stack.addLast(i);
                else flag = true;
            }
        return max;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.