My java solution based on Maximum Rectangle in Histogram with explanation
We can apply the maximum in histogram in each row of the 2D matrix. What we need is to maintain an int array for each row, which represent for the height of the
We can apply the maximum in histogram in each row of the 2D matrix. What we need is to maintain an int array for each row, which represent for the height of the histogram.\n\nPlease refer to https://leetcode.com/problems/largest-rectangle-in-histogram/      first.\n\n\nSuppose there is a 2D matrix like\n\n1 1 0 1 0 1\n\n0 1 0 0 1 1\n\n1 1 1 1 0 1\n\n1 1 1 1 0 1\n\n\nFirst initiate the height array as 1 1 0 1 0 1, which is just a copy of the first row. Then we can easily calculate the max area is 2.\n\nThen update the array. We scan the second row, when the matrix[1][i] is 0, set the height[i] to 0; else height[i] += 1, which means the height has increased by 1. So the height array again becomes 0 2 0 0 1 2. The max area now is also 2.\n\nApply the same method until we scan the whole matrix. the last height arrays is 2 4 2 2 0 4, so the max area has been found as 2 * 4 = 8.\n\nThen reason we scan the whole matrix is that the maximum value may appear in any row of the height.\n\n\nCode as follows: \n\n    public class Solution {\n    public int maximalRectangle(char[][] matrix) {\n        if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;\n        \n        int[] height = new int[matrix[0].length];\n        for(int i = 0; i < matrix[0].length; i ++){\n            if(matrix[0][i] == '1') height[i] = 1;\n        }\n        int result = largestInLine(height);\n        for(int i = 1; i < matrix.length; i ++){\n            resetHeight(matrix, height, i);\n            result = Math.max(result, largestInLine(height));\n        }\n        \n        return result;\n    }\n    \n    private void resetHeight(char[][] matrix, int[] height, int idx){\n        for(int i = 0; i < matrix[0].length; i ++){\n            if(matrix[idx][i] == '1') height[i] += 1;\n            else height[i] = 0;\n        }\n    }    \n    \n    public int largestInLine(int[] height) {\n        if(height == null || height.length == 0) return 0;\n        int len = height.length;\n        Stack<Integer> s = new Stack<Integer>();\n        int maxArea = 0;\n        for(int i = 0; i <= len; i++){\n            int h = (i == len ? 0 : height[i]);\n            if(s.isEmpty() || h >= height[s.peek()]){\n                s.push(i);\n            }else{\n                int tp = s.pop();\n                maxArea = Math.max(maxArea, height[tp] * (s.isEmpty() ? i : i - 1 - s.peek()));\n                i--;\n            }\n        }\n        return maxArea;\n    }\n    \n\n}
['Dynamic Programming', 'Java']