85. 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.

链接： http://leetcode.com/problems/maximal-rectangle/

题解：

题目就比较难理解。我一看containing all ones，直接return 长 x 宽，果断fail了。正确的意思应该是find the largest rectangle containing only ones and return its area。

Brute force - O(m³ x n³) 遍历整个数组，先找到lower-left，接下来找到upper-right，然后探测是否只包括1，同时与current best candidate 进行比较。

Region Grow - O(m² x n²)

DP - O(m² x n)

下面是用largest histgram的方法来做 - 对每一行cache 元素'1'的个数，当前元素为'0'时清零当前height。之后对每行进行一个"getLargestHistogram" 运算，来得到当前行的最大rectangle结果，最后和global max进行比较。Reference 1里是一个哥们1998年写的文章，就是关于这一题，很详细，为他点个赞学习了。 Heights数组的存在就是cache从row0到当前row为止在row上的1的数目，每完成一行cache，我们都必须对当前的heights数组，也就是cache的结果进行find largest rectangle in histogram的操作，否则到下一行的话有可能有些结果就被清零了。相当于computer 一个local max，再尝试去update一个global的max。

Time Complexity - O(mn)， Space Complexity - O(n)。

public class Solution {
    public int maximalRectangle(char[][] matrix) {
        if(matrix == null || matrix.length == 0)
            return 0;
        int max = 0;
        int[] heights = new int[matrix[0].length];
        
        for(int i = 0; i < matrix.length; i++) {            // O(n),  n = matrix.length;
            for(int j = 0; j < matrix[0].length; j++) {     // O(m),  m = matrix[0].length;
                if(matrix[i][j] == '1')                     // cache '1' in historgram array heights[]
                    heights[j]++;
                else
                    heights[j] = 0;
            }
            max = Math.max(max, findLargestRectangleInHistogram(heights));   // for each row, fine max rectangle,  O(m) operation
        }
        
        return max;
    }
    
    private int findLargestRectangleInHistogram(int[] heights) {        // find Larget Rectangle in Histogram
        if(heights == null || heights.length == 0)
            return 0;
        int[] h = new int[heights.length + 1];
        h = Arrays.copyOf(heights, heights.length + 1);
        int i = 0, max = 0;
        Stack<Integer> stack = new Stack<>();
        
        while(i < h.length) {
            if(stack.isEmpty() || h[i] >= h[stack.peek()])
                stack.push(i++);
            else {
                int tmp = stack.pop();
                max = Math.max(max, h[tmp] * (stack.isEmpty() ? i : ((i - 1) - stack.peek())));
            }
        }
        
        return max;
    }
}

有的时候不是自己不会做，而是见识太少。绝大部分的面试题都是有踪迹可循，像这道题，或者大整数乘除法，又或者滑雪。所以我认为题海战术是一定有效的。进了公司之后的发展另说，先进入好公司，赶上这波IT繁荣的尾巴，才是目前阶段最重要的。

二刷：

刚做完84，所以做85就轻松一些。方法还是跟一刷一样。下面我们理一理思路。

首先我们明确目的，是要求整个matrix矩阵中，只包含1的最大矩阵。我们可以套用上一题目中，求一个histogram中最大的rectangle的方法。

假如当前行row[i] = '0'，则我们清零accumulatedLen[i]
否则我们累积每个1， accumulatedLen[i] += 1

每次计算完一行的accumulatedLen数组时，我们就调用计算largestRectInHistogram的方法，来尝试更新max
最后返回max

Java:

Time Complexity - O(mn)， Space Complexity - O(n)

public class Solution {
    public int maximalRectangle(char[][] matrix) {
        if (matrix == null || matrix.length == 0) {
            return 0;
        }
        int colNum = matrix[0].length;
        int[] accumulatedHeights = new int[colNum];
        int max = 0;
        LinkedList<Integer> list = new LinkedList<>();
        for (char[] row : matrix) {
            list.clear();
            for (int i = 0; i < colNum; i++) {
                accumulatedHeights[i] = row[i] == '0' ? 0 : accumulatedHeights[i] + 1;
            }
            max = Math.max(calcLargestHist(accumulatedHeights, list), max);
        }
        return max;
    }
    
    private int calcLargestHist(int[] heights, LinkedList<Integer> list) {
        if (heights == null || heights.length == 0) {
            return 0;
        }
        int i = 0, max = 0;
        while (i < heights.length) {
            if (list.size() == 0 || heights[i] >= heights[list.peekLast()]) {
                list.addLast(i++);
            } else {
                int lastIndex = list.pollLast();
                max = Math.max(max, heights[lastIndex] * (list.size() == 0 ? i : (i - 1) - list.peekLast()));
            }
        }
        while (list.size() > 0) {
            int lastIndex = list.pollLast();
            max = Math.max(max, heights[lastIndex] * (list.size() == 0 ? i : (i - 1) - list.peekLast()));
        }
        return max;
    }
}

三刷:

依然是使用了一刷二刷的办法，利用上一题来求解。然而@morrischen2008的DP方法更为优雅，放在reference里，需要再进一步好好学习。

Java:

Time Complexity - O(mn)， Space Complexity - O(mn)

public class Solution {
    public int maximalRectangle(char[][] matrix) {
        if (matrix == null || matrix.length == 0) return 0;
        int colNum = matrix[0].length;
        int[] heights = new int[colNum];
        int max = 0;
        for (char[] row : matrix) {
            for (int j = 0; j < colNum; j++) {
                if (row[j] == '1') heights[j]++;
                else heights[j] = 0;
            }
            max = Math.max(max, getLargestRectangleArea(heights));
        }
        return max;
    }
    
    private int getLargestRectangleArea(int[] heights) {
        if (heights == null || heights.length == 0) return 0;
        Stack<Integer> stack = new Stack<>();
        int max = 0, idx = 0;
        while (idx <= heights.length) {
            int curHeight = (idx != heights.length) ? heights[idx] : 0;
            if (stack.isEmpty() || curHeight >= heights[stack.peek()]) {
                stack.push(idx++);
            } else {
                int height = heights[stack.pop()];
                int len = stack.isEmpty() ? idx : (idx - 1 - stack.peek());
                max = Math.max(max, height * len);
            }
        }
        return max;
    }
}

测试：

Reference:

http://www.drdobbs.com/database/the-maximal-rectangle-problem/184410529

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

https://leetcode.com/discuss/20240/share-my-dp-solution

https://leetcode.com/discuss/5198/a-o-n-2-solution-based-on-largest-rectangle-in-histogram

https://leetcode.com/discuss/52670/solution-based-maximum-rectangle-histogram-with-explanation

https://leetcode.com/discuss/97731/solution-largest-rectangle-histogram-solved-stack-simulation