Maximal Rectangle

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.

https://leetcode.com/problems/maximal-rectangle/

Solution I: brute force O(N^3)

取所有前面最小的延伸距离乘以当前离第一行的行数

http://www.cnblogs.com/lichen782/p/leetcode_maximal_rectangle.html

/**
     * 以给出的坐标作为左上角，计算其中的最大矩形面积
     * @param matrix
     * @param row 给出坐标的行
     * @param col 给出坐标的列
     * @return 返回最大矩形的面积
     */
    private int maxRectangle(char[][] matrix, int row, int col) {
        int minWidth = Integer.MAX_VALUE;
        int maxArea = 0;
        for (int i = row; i < matrix.length && matrix[i][col] == '1'; i++) {
            int width = 0;
            while (col + width < matrix[row].length
                    && matrix[i][col + width] == '1') {
                width++;
            }
            if (width < minWidth) {// 如果当前宽度小于了以前的最小宽度，更新它，为下面的矩形计算做准备
                minWidth = width;
            }
            int area = minWidth * (i - row + 1);
            if (area > maxArea)
                maxArea = area;
        }
        return maxArea;
    }

Solution II: Optimized O(N^2)

find max area in histogram as a routine to calculate each row

why n+1 in height:

height[i][n] == 0, manually push 0 to stack to calculate all the elements in stack

check the code for max rectangle for histogram

public class Solution {
    public int maximalRectangle(char[][] matrix) {
        int m = matrix.length;

        if (m == 0) {
            return m;
        }

        int n = matrix[0].length;

        int[][] height = new int[m][n+1]; // why n+1

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '0') {
                    height[i][j] = 0;
                } else {
                    height[i][j] = i == 0 ? 1 : height[i-1][j] + 1;
                }
            }
        }

        int max = 0;

        for (int i = 0; i < m; i++) {
            int area = maxInLine(height[i]);
            max = Math.max(area, max);
        }

        return max;
    }

    public int maxInLine(int[] height) {
        int max = 0;

        Stack<Integer> stack = new Stack<>();
        int i = 0;
        while (i < height.length) {
            if (stack.isEmpty() || height[i] >= height[stack.peek()]) {
                stack.push(i);
                i++;
            } else {
                int n = stack.pop();
                int curr = height[n] * (stack.isEmpty() ? i : i - stack.peek() - 1);
                max = Math.max(max, curr);
            }
        }

        return max;
    }
}