Java Solution Beat 86%, 11ms


  • 0
    J

    The idea is come from "Largest Rectangle in Histogram" question, I use one height array to record the height, the trick part is how to calculate the square. The most important condition is right - left must be less than height[right], this is because if the right - left > height[right], the max area will not exist in that area.

    private int getSquareArea(int[] height){
        int maxArea = 0;
        for (int left = 0; left < height.length; left++){
            int right = left, minHeight = height[left];
            while (right < height.length && height[right] != 0 && right - left <= height[right]){
                minHeight = Math.min(minHeight, height[right++]);
            }
            int width = right - left;
            int edge = Math.min(minHeight, width);
            maxArea = Math.max(edge * edge, maxArea);
        }
        return maxArea;
    }
    
    public int maximalSquare(char[][] matrix) {
        if (matrix == null || matrix.length == 0){
            return 0;
        }
        int[] height = new int[matrix[0].length];
        int maxArea = 0;
        for (int rowIndex = 0; rowIndex < matrix.length; rowIndex++){
            for (int colIndex = 0; colIndex < matrix[0].length; colIndex++){
                if (matrix[rowIndex][colIndex] == '0'){
                    height[colIndex] = 0;
                }else{
                    height[colIndex] += 1;
                }
            }
            maxArea = Math.max(maxArea, getSquareArea(height));
        }
        return maxArea;
    }

Log in to reply
 

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