Using TreeMap and one stack - Java solution


  • 0
    I

    The TreeMap takes care of min values. Just have to keep updating it.

    public class MinStack {
    
        /** initialize your data structure here. */
        Map<Integer,Integer> map;
        Stack<Integer> stack;
        
        public MinStack() {
            stack = new Stack<>();
            map = new TreeMap<>();
        }
        
        public void push(int x) {
            map.put(x,map.getOrDefault(x,0)+1);
            stack.push(x);
        }
        
        public void pop() 
        {
            if(!stack.isEmpty())
            {
                int x = stack.pop();
                
                if(map.get(x)==1)
                    map.remove(x);
                else    
                    map.put(x,map.get(x)-1);
            }
        }
        
        public int top() 
        {
            return stack.peek();    
        }
        
        public int getMin() {
            return map.entrySet().iterator().next().getKey();      
        }
    }
    
    /**
     * Your MinStack object will be instantiated and called as such:
     * MinStack obj = new MinStack();
     * obj.push(x);
     * obj.pop();
     * int param_3 = obj.top();
     * int param_4 = obj.getMin();
     */
    

Log in to reply
 

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