最小栈

原题链接

使用的方法

栈

解题思路

• 设计一个支持 push、pop、top 操作，并能在常数时间内检索到最小元素的栈。
• 我们可以使用两个栈来实现这个功能：一个主栈用于存储所有的元素，另一个辅助栈用于存储当前主栈中的最小元素。
• 每当我们向主栈中推入一个元素时，我们将其与当前最小元素进行比较，并将较小的元素推入辅助栈中。这样，辅助栈的顶部始终保持着当前主栈中的最小元素。
• 当我们弹出主栈的顶部元素时，我们也需要弹出辅助栈的顶部元素，以确保辅助栈始终与主栈保持同步。
• 通过这种方式，我们可以在常数时间内获取主栈中的最小元素，同时保持其他操作的效率。

代码实现

class MinStack {
    Deque<Integer> stack;
    Deque<Integer> minStack;

    public MinStack() {
        stack = new LinkedList<Integer>();
        minStack = new LinkedList<Integer>();
        minStack.push(Integer.MAX_VALUE);        
    }
    
    public void push(int val) {
        stack.push(val);
        minStack.push(Math.min(minStack.peek(),val));
    }
    
    public void pop() {
        stack.pop();
        minStack.pop();
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return minStack.peek();
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */