Any one help me to figure out why it get time limit exceeded when one line code is omited?


  • 0
    L

    First I must say it's not a good solution to this question cuz it's time costing for push(). The idea is to use a double linked list to keep track of the order of all elements in the stack. This code got AC, but I just want to know why it got time limit exceeded when I didn't set the min node's successor to null in the pop() method? (It's commented in the code.)

    Thank you so much for your help!!!

    class MinStack {
        StackNode top;
        StackNode min;
        public void push(int x) {
            StackNode tmp = new StackNode(x);
            if(top==null){
                top = tmp;
                min = tmp;
            }
            else{
                tmp.next = top;
                top = tmp;
                if(x>min.val){
                    StackNode helper = min;
                    while(helper.precedor!=null&&helper.precedor.val<x){
                    	helper = helper.precedor;
                    }
                    tmp.precedor = helper.precedor;
                    if(helper.precedor!=null) helper.precedor.successor = tmp;
                    helper.precedor = tmp;
                    tmp.successor = helper;
                }
                else{
                    tmp.precedor = this.min;
                    this.min.successor = tmp;
                    this.min = tmp;
                }
            }
        }
    
        public void pop() {
            if(top==null) return;
            StackNode tmp = top;
            top = top.next;
            if(tmp==min) {
                min = min.precedor;
                if(min!=null) min.successor = null; //why got time limit exceeded without this line ??????????????
            }
            else{
                if(tmp.precedor!=null){
                    tmp.precedor.successor = tmp.successor;
                }
                tmp.successor.precedor = tmp.precedor;
            }
            
        }
    
        public int top() {
            return this.top.val;
        }
    
        public int getMin() {
            return this.min.val;
        }
    }
    
    class StackNode{
        int val;
        StackNode next;
        StackNode precedor; //bigger than val
        StackNode successor; //smaller than val. Use this extra space to reduce the time cost for pop() to O(1).
        StackNode(int x){ val = x;}
    }

Log in to reply
 

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