Share my Java solution with time O(n^2), space O(n)


  • 0
    D

    Beats 48.19% of java submissions.

    // Time : O(n^2) Space : O(n)
    public int maximalRectangle(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length ==0) return 0;
        int[] hist = new int[matrix[0].length];
        // Start with the first row
        for (int i = 0 ; i < matrix[0].length ; i++) {
            hist[i] = matrix[0][i] == '1' ? 1 : 0;
        }
        int max = maxHist(hist);
        for (int i = 1 ; i < matrix.length ; i++) {
            for (int j = 0 ; j < matrix[0].length ; j++) {
                if (matrix[i][j] == '0') {
                    hist[j] = 0;
                } else {
                    hist[j] = hist[j] + 1;
                }
            }
            max = Math.max(max, maxHist(hist));
        }
        
        return max;
    }
    
    private int maxHist(int[] hist) {
        Stack<Integer> stack = new Stack<>();
        int n = hist.length;
        int i = 0;
        int max = 0;
        while(i < n) {
            while (!stack.isEmpty() && hist[i] < hist[stack.peek()]) {
              max = Math.max(max, hist[stack.pop()] * (i - (stack.isEmpty() ? 0 : stack.peek() + 1)));
            }
            stack.push(i++);
        }
        
        while(stack.isEmpty() == false) {
            max = Math.max(max, hist[stack.pop()] * (n - (stack.isEmpty() ? 0 : stack.peek() + 1)));
        }
        return max;
    }

Log in to reply
 

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