Maximal Rectangle.java

H
1521321013
tags: Array, Hash Table, DP, Stack

#### 方法1: monotonous stack
分解开来, 其实是'Largest Rectangle in Histogram', 只不过这里要自己model heights.
一个2D array里面的rectangle, 最终也是用height * width做出来的.
巧妙在于, 把每一行当做底边, 算出这个底边, 到顶部的height: 
- 如果底边上的一个value==0, 那么算作没有height(以这个底边做rectangle, value==0的位置是空中楼阁, 不能用)
- 如果底边上的value==1, 那么就把上面的height加下来, 做成histogram

如果看具体实例, 有些row似乎是白算的, 但是没有办法, 这是一个搜索的过程, 最终会比较出最优解.

#### 方法2: DP
Coordinate DP?

```
/*
Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.

For example, given the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Return 6.
*/


/*
Thoughts:
Different form of 'Largest Rectangle in Histogram': 
break the problem down then we are dealing with m list of histogram.
Each row (from top to bottom), can be modeled as histogram: sum 1's from top to the current row.

After that point, just calculate largest rectangle in each modelded histogram row, using stack.
*/
class Solution {
    public int maximalRectangle(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {
            return 0;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] heightMap = new int[m][n];
        
        // Prepare height map
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '0') {
                    heightMap[i][j] = 0;
                } else {
                    heightMap[i][j] = i == 0 ? 1 : heightMap[i - 1][j] + 1;
                }
            }
        }
        
        int maxArea = 0;
        for (int i = 0; i < m; i++) {
            maxArea = Math.max(maxArea, findLargestRectInHistogram(heightMap[i]));
        }

        return maxArea;
    }
    
    private int findLargestRectInHistogram(int[] height) {
        Stack<Integer> stack = new Stack<>();
        int m = height.length;
        int max = 0;
        for (int i = 0; i <= m; i++) {
            int currHeight = i == m ? -1 : height[i];
            while (!stack.isEmpty() && currHeight <= height[stack.peek()]) {
                int peekHeight = height[stack.pop()];
                int width = stack.isEmpty() ? i : i - stack.peek() - 1;
                max = Math.max(max, peekHeight * width);
            }
            stack.push(i);
        }
        return max;
    }
}
```