Very Very Easy to Understand Java Solution Based on Largest Rectangle Histogram


  • 0
    L

    My java solution. It's very easy to understand if you know Largest Rectangle in Histogram.

    public int maximalRectangle(char[][] matrix) {
        if (matrix == null || matrix.length == 0) return 0;
        int m = matrix.length, n = matrix[0].length;
        int maxArea = 0;
        int[] heights = new int[n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '1') heights[j] += 1;
                else heights[j] = 0;
            }
            maxArea = Math.max(maxArea, maxAreaHistogram(heights));
        }
        return maxArea;
    }
    
    private int maxAreaInHistogram(int[] heights) {
        Stack<Integer> stack = new Stack<Integer>();
        int maxArea = 0;
        for (int i = 0; i <= heights.length; i++) {
            int height = i == heights.length ? 0 : heights[i];
            while (!stack.isEmpty() && heights[stack.peek()] >= height) {
                int lastHeight = heights[stack.pop()];
                int width = stack.isEmpty() ? i : i - stack.peek() - 1;
                maxArea = Math.max(maxArea, lastHeight * width);
            }
            stack.push(i);
        }
        return maxArea;
    }
    
    

Log in to reply
 

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