Share my accepted Java solution.


  • 0
    I
    class MinStack {
        private  ArrayList<Integer> minPosition;
        private  ArrayList<Integer> array;
    
        MinStack() {
            minPosition = new ArrayList<Integer>();
            array = new ArrayList<Integer>();
        }
        public void push(int x) {
            if (array.size() == 0) {
                minPosition.add(0);
            } else {
                int size = minPosition.size();
                if (x < array.get(minPosition.get(size - 1))) {
                    minPosition.add(array.size());
                } else {
                    minPosition.add(minPosition.get(size - 1));
                }
            }
            array.add(x);
        }
    
        public void pop() {
            array.remove(array.size()-1);
            minPosition.remove(minPosition.size()-1);
        }
    
        public int top() {
            return array.get(array.size()-1);
        }
    
        public int getMin() {
            return array.get(minPosition.get(minPosition.size()-1));
        }
    }

  • 0
    L

    A funny thing here:

    My structure is similar with yours, but I used the arraylist to store the int value instead of the min position. But the system always gives me the runtime exceed error.

    Here is my code:

    List<Integer> min;
    List<Integer> storage;
    
    public MinStack(){
    	this.min =  new ArrayList<Integer>();
    	this.storage = new ArrayList<Integer>();
    }
    public void push(int x) {
        this.storage.add(x);
        if (this.min.isEmpty()){
        	this.min.add(x);
        }
        else{
        	int size = min.size();
        	if (x<this.min.get(size-1)){
        		this.min.add(x);
        	}
        	else{
        		this.min.add(min.get(size-1));
        	}
        }
    }
    
    public void pop() {
    	if(this.storage.isEmpty()){
    		return;
    	}
    	this.min.remove(this.storage.get(this.storage.size()-1));
        this.storage.remove(this.storage.size()-1);
    }
    
    public int top() {
        return this.storage.get(this.storage.size()-1);
    }
    
    public int getMin() {
        if (this.min.isEmpty()){
        	return 0;
        }
        return this.min.get(0);
    }
    

    When I change my arraylist to store all index like yours, code is accepted. I wonder why it happened.


  • 0
    I

    Your logic in pop is wrong, you should remove the last element in min.Also, the getMin should return the last element,not the first.The right solution is in my following answer.


  • 0
    I
    class MinStack {
        List<Integer> min;
        List<Integer> storage;
        
        public MinStack(){
            this.min =  new ArrayList<Integer>();
            this.storage = new ArrayList<Integer>();
        }
        public void push(int x) {
            this.storage.add(x);
            if (this.min.isEmpty()){
                this.min.add(x);
            }
            else{
                int size = min.size();
                if (x<this.min.get(size-1)){
                    this.min.add(x);
                }
                else{
                    this.min.add(min.get(size-1));
                }
            }
        }
        
        public void pop() {
            if(this.storage.isEmpty()){
                return;
            }
            this.min.remove(this.min.get(this.min.size()-1));
            this.storage.remove(this.storage.size()-1);
        }
        
        public int top() {
            return this.storage.get(this.storage.size()-1);
        }
        
        public int getMin() {
            if (this.min.isEmpty()){
                return 0;
            }
            return this.min.get(this.min.size()-1);
        }
    }

  • 0
    L

    Yes! That helps me to fix that problem!
    Thank you for helping me! :D


Log in to reply
 

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