Java easy to understand two stacks solution


  • 4
    L

    The difficult of this problem is how to get the min element from stack in constant time. The way I approach this problem is to use another stack(min stack) which records a sequence of minimal values as elements being pushed into the stack. In this way, we can be sure that the top element on the stack must be the minimal element. Finally, we maintaining the stack's min element up to date by checking whether the top element in the min stack is the same with the top element in the normal stack. If there are the same, we pop both stack. Otherwise, we only pop the normal stack.

    class MinStack {
        private Stack<Integer> st = new Stack<Integer>();
        private Stack<Integer> min_st = new Stack<Integer>();
        
        public void push(int x) {
            if(min_st.isEmpty() || min_st.peek()>=x) min_st.push(x); 
            st.push(x);
        }
    
        public void pop() {
            if((int)st.peek()==(int)min_st.peek()) min_st.pop();
            st.pop();
        }
    
        public int top() {
            return st.peek();
        }
    
        public int getMin() {
            return min_st.peek();
        }
    }

Log in to reply
 

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