/** * 设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。 * * push(x) —— 将元素 x 推入栈中。 * pop() —— 删除栈顶的元素。 * top() —— 获取栈顶元素。 * getMin() —— 检索栈中的最小元素。 */ import java.util.Deque; import java.util.LinkedList; /** * 用一个辅助栈：维护一个变量为当前栈的最小值，每次push的时候 * 往辅助栈内插入最小值的元素 */ public class MinStack { Deque xStack; Deque minStack; public MinStack() { xStack = new LinkedList<>(); minStack = new LinkedList<>(); minStack.push(Integer.MAX_VALUE); } public void push(int x) { xStack.push(x); minStack.push(Math.min(x, minStack.peek())); } public void pop() { xStack.pop(); minStack.pop(); } public int top() { return xStack.peek(); } public int getMin() { return minStack.peek(); } }