inspired by largest rectangle in histogram


  • 0
    Y
    public int maximalRectangle(char[][] matrix) {
        if(matrix == null || matrix.length == 0) return 0;
        int max = largestRectangleArea(matrix[0]);
        for(int i = 1; i<matrix.length; i++){
            for(int j = 0 ; j<matrix[0].length; j++){
                if(matrix[i][j] == '1'){
                    matrix[i][j] += (char)(matrix[i-1][j] - 48);
                }
            }
            int curMax = largestRectangleArea(matrix[i]);
            if(curMax > max) max = curMax;
        }
        return max;
    }
    
    public int largestRectangleArea(char[] heights) {
        Deque<Integer> stack = new LinkedList();
        int max = 0;
        for(int i = 0; i<=heights.length; i++){
            while(!stack.isEmpty() && (i == heights.length || heights[stack.peek()] >= heights[i])){
                int curMax = (heights[stack.pop()] - 48) * (stack.isEmpty() ? i: i-stack.peek()-1);
                if(curMax > max) max = curMax;
            }
            stack.push(i);
        }
        return max;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.