Input:

 [

[” 1 “, “0”, “1”, “0” and “0”].

[” 1 “, “0”, “1”, “1”, “1”].

[” 1 “, “1”, “1”, “1”, “1”].

[” 1 “, “0”, “0”, “1”, “0”]

] 

Output: 6


This problem can be converted to 84. The largest rectangle in the bar chart (leetcode)




For traversing the rows or columns of a two-dimensional array, the conversion bits find the maximum matrix area that can be formed by a contiguous height array of each row



Code:

    public int largestRectangleArea(int[] heights) {
        if(heights==null||heights.length<=0)
            return 0;
        Stack<Integer> stack = new Stack<>();
        int reuslt = 0;
        for(int i=0; i<heights.length; ++i){if(stack.isEmpty()||heights[stack.peek()]<=heights[i]){
                stack.add(i);
            }
            else{
                while(! stack.isEmpty()&&heights[stack.peek()]>heights[i]) {int k = stack.pop();
                    int left = stack.isEmpty() ? -1 : stack.peek();
                    int right = i;
                    reuslt = Integer.max(reuslt, (k - left + right - k - 1) * heights[k]); } stack.add(i); }}while(! stack.isEmpty()){int k = stack.pop();
            int left = stack.isEmpty() ? -1 : stack.peek();
            int right = heights.length;
            reuslt = Integer.max(reuslt, (k - left + right - k - 1) * heights[k]);
        }
        return reuslt;
    }






    public int maximalRectangle(char[][] matrix) {
        if(matrix==null||matrix.length<=0)
            return 0;
        int[] nu =  new int[matrix[0].length];
        int result = 0;
        for(int i=0; i<matrix.length; ++i){for(int k=0; k<nu.length; ++k){if(matrix[i][k]=='1')
                    nu[k] += 1;
                else
                    nu[k] = 0;
            }
            result = Integer.max(result,largestRectangleArea(nu));
        }
        return result;
    }

Copy the code