85. Maximal Rectangle

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.

思路：还是不会

public class Solution {
    public int maximalRectangle(char[][] matrix) {
        if matrix

        int nRows = matrix.length;
        int nCols = matrix[0].length;
        int max = 0;
        for (int i=0;i<nRows;i++){
            int[] heights = getHeights(matrix,i);
            // System.out.println(Arrays.toString(heights));
            max = Math.max(max,largestRectangleArea(heights));
        }
        return max;
    }

    public int[] getHeights(char[][] matrix,int i){
        int[] heights = new int[matrix[0].length];
        for (int j=0;j<matrix[0].length;j++){
            int h = 0;
            for(int k=i;k>=0;k--){
                if (matrix[k][j]=='0'){
                    break;
                }else{
                    h++;
                }
            }
            heights[j] = h;
        }
        return heights; 
    }


    public int largestRectangleArea(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }

        Stack<Integer> stack = new Stack<Integer>();

        int max = 0;
        int i = 0;

        while (i < height.length) {
            //push index to stack when the current height is larger than the previous one
            if (stack.isEmpty() || height[i] >= height[stack.peek()]) {
                stack.push(i);
                i++;
            } else {
            //calculate max value when the current height is less than the previous one
                int p = stack.pop();
                int h = height[p];
                int w = stack.isEmpty() ? i : i - stack.peek() - 1;
                max = Math.max(h * w, max);
            }

        }

        while (!stack.isEmpty()) {
            int p = stack.pop();
            int h = height[p];
            int w = stack.isEmpty() ? i : i - stack.peek() - 1;
            max = Math.max(h * w, max);
        }

        return max;
    }
}