Why dp is much faster than stack?


  • 0
    B

    I think both time complexity are O(m*n), where m is matrix.length, and n is matrix[0].length.
    and dp based algorithm will traverse two more times than stack based algorithm each row. So I am confused about the fact that dp is much faster than stack. Can anyone help?


    DP based Algorithm: 10ms

    public class Solution {
        public int maximalRectangle(char[][] matrix) {
            int m = matrix.length;
            if(m == 0) return 0;
            
            int n = matrix[0].length;
            if(n == 0) return 0;
            
            int maxRec = 0;
            
            int [] left = new int[n];
            int [] right = new int[n];
            int [] height = new int[n];
            
            for(int i = 0; i<n; ++i) right[i] = n;
            for(int i = 0; i<m; ++i){
                //calculate heights
                for(int j = 0;j<n; ++j){
                    height[j] = matrix[i][j] == '0'? 0: height[j]+1;
                }
                
                int cur_left = 0;
                for(int j = 0; j<n; ++j){
                    if(matrix[i][j] != '0') left[j] = Math.max(left[j], cur_left);
                    else{
                        left[j] = 0;
                        cur_left = j + 1;
                    }
                }
                int cur_right = n;
                for(int j =n-1; j>=0; --j){
                    if(matrix[i][j] != '0') right[j] = Math.min(right[j], cur_right);
                    else{
                        right[j] = n;
                        cur_right = j;
                    }
                }
                
                for(int j = 0; j<n; ++j){
                    maxRec = Math.max(maxRec, height[j] *(right[j]-left[j]));
                }
            }
            return maxRec;
        }
    }
    

    Stack based Algorithm: 75ms

    public class Solution {
        public int maximalRectangle(char[][] matrix) {
            int m = matrix.length;
            if(m == 0) return 0;
            int n = matrix[0].length;
            if( n== 0) return 0;
            
            int [] height = new int[n];
            int maxRec = 0;
            Stack<Integer> stack = new Stack<>();
            
            stack.push(-1);
            for(int i = 0;i<m;++i){
                for(int j =0; j<n;++j){
                    height[j] = matrix[i][j]=='0'?0:height[j] +1;
                    while(stack.peek() != -1 && height[j] <= height[stack.peek()]){
                        int end = stack.pop();
                        maxRec = Math.max(maxRec, height[end] * (j-stack.peek()-1));
                    }
                    stack.push(j);
                }
                
                while(stack.peek() != -1){
                    int h = height[stack.pop()];
                    maxRec = Math.max(maxRec, h *(n-1-stack.peek()));
                }
            }
            return maxRec;
        }
    }
    

  • 0

    @biwuxia You are using stack object instead of primitive array to store the heights, which can be the major reason. Perhaps you should try int [] stack; int top=-1 instead of Stack<Integer>.


Log in to reply
 

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