class Solution {

    public int maximalRectangle(char[][] matrix) {

        if(matrix.length == 0 ) return 0;

        int width = matrix[0].length;

        int height = matrix.length;

        int maxArea = 0;

        int area;

        //按列动态规划，求出到此位置最多连续为1的次数

        int[][] dp = new int[height][width];

        for(int i = 0; i < width; i++){

            for(int j = 0; j < height; j++){

                dp[j][i] = matrix[j][i] - '0';

                if(matrix[j][i] == '1' && j > 0){

                    dp[j][i] += dp[j-1][i];

                }

            }

        }

        //按行动态规划，求出最大面积

        for(int i = 0; i < height; i++){

            area = largestRectangleArea(dp[i]);

            if(area > maxArea) maxArea = area;

        }

        return maxArea;

    }

    public int largestRectangleArea(int[] heights) {

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

        if(heights.length == 0) return 0;

        int leftIndex;

        int topIndex;

        int area;

        int maxArea = 0;

        int i = 0;

        while(i < heights.length){

            if(st.empty() || heights[i] >= heights[st.peek()]){

                st.push(i);

                i++;

            }

            else{

                topIndex = st.peek();

                st.pop();

                leftIndex = st.empty()?0:st.peek()+1; //如果是空，说明从头开始的所有高度都比heights[topIndex]高

                area = ((i-1)-leftIndex + 1) * heights[topIndex];

                if(area > maxArea) maxArea = area;

            }

        }

        while(!st.empty()){ //没有比栈顶元素小的元素让它出栈

            topIndex = st.peek();

            st.pop();

            leftIndex = st.empty()?0:st.peek()+1;

            area = ((i-1)-leftIndex + 1) * heights[topIndex];

            if(area > maxArea) maxArea = area;

        }

        return maxArea;

    }

}