Java space efficient AC solution without using Java's Stack class


  • 2
    I

    class MinStack {
    int min;
    ArrayList<Integer> ar;
    ArrayList<Integer> minList;
    HashMap<Integer,Integer> map;

    MinStack() {
        min = Integer.MAX_VALUE;
        ar = new ArrayList<Integer>();
        minList = new ArrayList<Integer>(); 
        map = new HashMap<Integer,Integer>();
    }
    
    public void push(int x) {
        if (min >= x) {
            min = x;
            
            if (map.containsKey(x)) {
                int count = map.get(x);
                map.put(x,count+1);
            }
            else {
                minList.add(x);
                map.put(x,1);
            }
        }
        ar.add(x);
    }
    
    public void pop() {
        int top = this.top();
        
        if (top == min) {
            int count = map.get(min);
            if (count > 1) {
                map.put(min, count - 1);
            }
            else {
                map.remove(min);
                minList.remove(minList.size()-1);
                if(minList.size() > 0) {
                    min = minList.get(minList.size()-1);
                }
                else {
                    min = Integer.MAX_VALUE;
                }
            }
        }
        ar.remove(ar.size()-1);
    }
    
    public int top() {
        return ar.get(ar.size()-1);
    }
    
    public int getMin() {
        return min;
    }
    

    }


Log in to reply
 

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