Help on "Memory Limit Exceeded" for Min Stack


  • 0
    F

    I am using the ArrayList to solve this "Min Stack" problem. Could someone help me why the judder says "Memory Limit Exceeded"? Thanks so much!

    class MinStack {
        ArrayList<Integer> St = new ArrayList<Integer>();
     
        void push(int x) {
            if(St.size()==0){
                St.add(1);         // the first element as the placeholder for the number of elements have the minimum value of the stack
                St.add(x);         // the second element as the placeholder for the minimum value of the stack
            }else if(x < St.get(1)){
                St.set(1, x);       // update the minimum value
                St.set(0, 1);       // update the number of minimum value
            }else if(x == St.get(1)){
                St.set(0, St.get(0)+1);      // update the number of minimum value
            }
            St.add(x);
        }
    
        void pop(){
            if(St.size()>2){
                if(this.top() == St.get(1)){
                    if(St.get(0)>1){               // more than one minimum values in the stack
                        St.set(0, St.get(0)-1);
                        St.remove(St.size()-1);
                    }else{                         // this is the only minimum value in the tack, then need to update the minimum value
                        St.remove(St.size()-1);
                        St.set(1, Integer.MAX_VALUE);
                        St.set(0, 1);
                        for(int i=2; i<St.size(); i++){        // find the minimum value
                            if(St.get(1) > St.get(i)) {
                                St.set(1, St.get(i));
                            }else if(St.get(1) == St.get(i)){
                                St.set(0, St.get(0)+1);
                            }
                            
                        }
                    
                    }
                }else{
                      St.remove(St.size()-1);    
                }
            }else{
                System.out.println("Stack is empty");
            }
        }
    
        int top() {
            return St.get(St.size()-1);
        }
    
        int getMin() {
            return St.get(1);
        }
    };

  • 0
    S

    I used java linkedlist ,accepted.


  • 0
    F

    could you share your code please?


  • 0

    How does your program ensure constant time pop()??


  • 0
    F

    en, that's a good question. Looks like I miss-understood the question itself. I thought only 'retrieving the minimum of the stack' need to be done in constant time. But obviously I'm wrong now :(


Log in to reply
 

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