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.

Solution1：轉直方圖后 利用84題 stack 方式求解

思路：
m次：先每行累計變成直方圖，如果元素為0，累積直方圖的位置是0.
每一次累積調用一下84題直方圖面積求最大。
最終求得全局最大。

Time Complexity: O(mn) Space Complexity: O(nn)

Solution2：DP

思路：
Time Complexity: O(mn) Space Complexity: O(mn)

Solution1 Code：

class Solution {
    public int maximalRectangle(char[][] matrix) {
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
        int[] heights = new int[matrix[0].length];
        
        int max = 0;
        for(int i = 0; i < matrix.length; i++) {
            for(int j = 0; j < matrix[0].length; j++) {
                if(matrix[i][j] == '1') {
                    heights[j]++;
                }
                else {
                    heights[j] = 0;
                }
            }
            int area = largestRectangleArea(heights);
            max = Math.max(max, area);
        }
        return max;
    }
    
    
    // directly copy from 84. Largest Rectangle in Histogram
    private int largestRectangleArea(int[] heights) {
        if(heights == null || heights.length == 0) return 0;
        
        int max = 0;
        
        Deque<Integer> stack = new ArrayDeque<>();
        
        for(int cur = 0; cur < heights.length; cur++) {
            // (1) 遇到增長的就將其index push至stack；
            if(stack.isEmpty() || heights[cur] >= heights[stack.peek()]) {
                stack.push(cur);
            }
            // (2) 遇到減的時候得到此柱上一個柱的右邊界：此柱。
            // 則能計算上一個柱以其自身的max = (其右邊界-左邊界) * 其高度
            else {
                int right_border = cur;
                int index = stack.pop();
                while(!stack.isEmpty() && heights[index] == heights[stack.peek()]) {  // 等高情況
                    index = stack.pop();
                }
                int left_border = stack.isEmpty() ? -1 : stack.peek();
                
                max = Math.max(max, (right_border - left_border - 1) * heights[index]);
                cur--; // 重新從此柱
            }
        }
        
        // 余下單調棧
        int right_border = stack.peek() + 1;
        while(!stack.isEmpty()) {
            int index = stack.pop();
            int left_border = stack.isEmpty() ? -1 : stack.peek();
            max = Math.max(max, (right_border - left_border - 1) * heights[index]);
        }
        return max;
    }
}

Solution2 Code：