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

  • 0

    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);
                top = tmp;
                min = tmp;
       = top;
                top = tmp;
                    StackNode helper = min;
                    	helper = helper.precedor;
                    tmp.precedor = helper.precedor;
                    if(helper.precedor!=null) helper.precedor.successor = tmp;
                    helper.precedor = tmp;
                    tmp.successor = helper;
                    tmp.precedor = this.min;
                    this.min.successor = tmp;
                    this.min = tmp;
        public void pop() {
            if(top==null) return;
            StackNode tmp = top;
            top =;
            if(tmp==min) {
                min = min.precedor;
                if(min!=null) min.successor = null; //why got time limit exceeded without this line ??????????????
                    tmp.precedor.successor = tmp.successor;
                tmp.successor.precedor = tmp.precedor;
        public int top() {
        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.