Piggybacking Maximal Rectangle, AC, 90%


  • 0
    Z

    none DP one, piggybacking 'maximal rectangle', to speed up, use array instead of Stack/ArrayDeque

    same as 'maximal rectangle', runtime is O(n^2)

    public int maximalSquareArrayStack(char[][] matrix) {
        if (matrix.length == 0) return 0;
    
        int col = matrix[0].length;
        int maxSq = 0;
    
        int[] sums = new int[col + 1];
        int[] stack = new int[col + 1];
        for (char[] row : matrix) {
            for (int i = 0; i < col; i++) {
                sums[i] = row[i] == '0' ? 0 : sums[i] + 1;
            }
            int pos = -1;
            int i = 0;
            while (i <= col) {
                if (pos == -1 || sums[i] >= sums[stack[pos]]) {
                    stack[++pos] = i++;
                } else {
                    int top = stack[pos--];
                    int min = Math.min(sums[top] , pos == -1? i: i - stack[pos] - 1);
                    maxSq = Math.max(maxSq, min * min);
                }
            }
        }
    
        return maxSq;
    }

Log in to reply
 

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