包含min函数的栈

设计一个支持push，pop，top等操作并且可以在O(1)时间内检索出最小元素的堆栈。

push(x)–将元素x插入栈中 pop()–移除栈顶元素 top()–得到栈顶元素 getMin()–得到栈中最小元素

样例 MinStack minStack = new MinStack(); minStack.push(-1); minStack.push(3); minStack.push(-4); minStack.getMin(); --> Returns -4 minStack.pop(); minStack.top(); --> Returns 3 minStack.getMin(); --> Returns -1

单调栈

时间复杂度O(1)

class MinStack { Stack<Integer> stack; Stack<Integer> min; public MinStack() { stack = new Stack<>(); min = new Stack<>(); } public void push(int x) { stack.push(x); if(min.empty() || x <= min.peek()){ min.push(x); }else{ min.push(min.peek()); } } public void pop() { stack.pop(); min.pop(); } public int top() { return stack.peek(); } public int getMin() { return min.peek(); } }