85. Maximal Rectangle

LeetCode Link

public int maximalRectangle(char[][] matrix) {
    if (matrix == null || matrix.length == 0|| matrix[0] == null || matrix[0].length == 0) {
        return 0;
    }
    int rows = matrix.length;
    int cols = matrix[0].length;
    int[][] heightMatrix = new int[rows][cols];
    for (int i = 0; i < cols; i++) {
        heightMatrix[0][i] = (matrix[0][i] == '0') ? 0 : 1;
    }
    for (int i = 1; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            heightMatrix[i][j] = (matrix[i][j] == '0') ? 0 : heightMatrix[i - 1][j] + 1;
        }
    }
    
    int maxArea = 0;
    for (int[] row: heightMatrix) {
        int currMax = largestRectangleArea(row);
        maxArea = Math.max(maxArea, currMax);
    }
    
    return maxArea;
}

// 84 Largest Rectangle in Histogram 题解 function
private int largestRectangleArea(int[] heights) {
    if (heights == null || heights.length == 0) {
        return 0;
    }
    int maxArea = 0;
    Stack<Integer> stack = new Stack<>();
    
    for (int i = 0; i <= heights.length; i++) {
        int h = (i == heights.length) ? 0 : heights[i];
        while (!stack.isEmpty() && heights[stack.peek()] > h) {
            int index = stack.pop();
            int leftBound = stack.isEmpty() ? -1 : stack.peek();
            int currArea = (i - leftBound - 1) * heights[index];
            maxArea = Math.max(maxArea, currArea);
        }
        stack.push(i);
    }
    
    return maxArea;
}