https://leetcode.com/problems/min-stack/description/ Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. push(x) -- Push element x onto stack. pop() -- Removes the element on top of the stack. top() -- Get the top element. getMin() -- Retrieve the minimum element in the stack. Example: MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> Returns -3. minStack.pop(); minStack.top(); --> Returns 0. minStack.getMin(); --> Returns -2. corner cases: 1)If the stack is empty, min() should return -1. 2)pop() - remove and return the top element, if the stack is empty, return -1 3)push(int element) - push the element to top top() - return the top element without remove it, if the stack is empty, return -1 4) min() - return the current min value in the stack.
这种写法 stack 1 stack 2 同步操作，stack 1 进来一个 stack2 也要进来一个。如果有特别多重复的数进来的情况，并且是一整块一样的数进来，那是可以被优化的。
1111111 222222 -1-1-1-1 111111 -2-2-2-2-2 33333
如果 进来的数字是交叉的，则优化空间有限: 1212121212
1 public class LC_155_MinStack { 2 3 private Deque stack ; 4 private Deque minStack ; 5 6 /** initialize your data structure here. */ 7 public LC_155_MinStack() { 8 stack = new LinkedList<>() ; 9 minStack = new LinkedList<>();10 }11 /*12 stack -2 0 -313 min -2 -2 -314 * */15 public void push(int x) {16 stack.push(x);17 if (minStack.isEmpty()){18 minStack.push(x);19 } else{20 if (minStack.peek() < x){21 minStack.push(minStack.peek());22 } else{23 minStack.push(x);24 }25 }26 }27 28 public void pop() {29 if (stack.isEmpty()) return ;30 stack.pop();31 minStack.pop();32 }33 //peek34 public int top() {35 if (stack.isEmpty()) return -1 ;36 return stack.peek() ;37 }38 39 public int getMin() {40 if (minStack.isEmpty()) return -1 ;41 return minStack.peek();42 }43 }