Leetcode - Maximum Rectangle

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

[balabala] 这题想到借用Largest Rectangle in Histogram的思路就比较简单了。计算行 i 时，以这行为底，计算每一列对应的“高度”，若某列元素为0，则高度为0，若为1，则高度=同列上一行高度 + 1。得出每列高度后，应用Largest Rectangle in Histogram的思路计算出该行对应的直方图中的最大矩形。遍历完所有行后得解。

 

    //method 1
    public int maximalRectangle(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
            return 0;
        int max = 0;
        int rows = matrix.length;
        int cols = matrix[0].length;
        int[] h = new int[cols];
        LinkedList<Integer> stack = new LinkedList<Integer>();
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                h[j] = matrix[i][j] == '1' ? h[j] + 1 : 0;
            }
            int j = 0;
            stack.clear();
            while (j < cols || !stack.isEmpty()) {
                if (stack.isEmpty() || (j < cols && h[j] >= h[stack.peek()])) {
                    stack.push(j++);
                } else {
                    int currH = h[stack.pop()];
                    while (!stack.isEmpty() && currH == h[stack.peek()]) {
                        stack.pop();
                    }
                    max = Math.max(max, currH * (stack.isEmpty() ? j : (j - stack.peek() - 1)));
                }
            }
        }
        return max;
    }

    

    // method2: more clear
    public int maximalRectangle(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
            return 0;
        int rows = matrix.length;
        int cols = matrix[0].length;
        int[] h = new int[cols + 1];
        int max = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (matrix[i][j] == '1')
                    h[j] += 1;
                else
                    h[j] = 0;
            }
            max = Math.max(max, getLargestRectangle(h));
        }
        return max;
    }
    
    // the last element in h[] is always 0
    private int getLargestRectangle(int[] h) {
        int max = 0;
        LinkedList<Integer> stack = new LinkedList<Integer>();
        int i = 0;
        while (i < h.length) {
            if (stack.isEmpty() || h[i] >= h[stack.peek()]) {
                stack.push(i++);
            } else {
                int currH = h[stack.pop()];
                while (!stack.isEmpty() && h[stack.peek()] == currH) {
                    stack.pop();
                }
                int left = stack.isEmpty() ? -1 : stack.peek();
                max = Math.max(max, currH * (i - left - 1));
            }
        }
        return max;
    }