Min Stack(包含min函数的栈)

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

getMin() — Retrieve the minimum element in the stack

问题的关键是getMin的时间复杂度是常量。最朴素的想法就是如下：

class MinStack {LinkedList<Integer> stack = new LinkedList<>();Integer min = Integer.MAX_VALUE;public void push(int x) {stack.push(x);if (x < min) {min = x;}}public void pop() {stack.pop();min = Integer.MAX_VALUE;for (Integer index : stack) {if (index < min) {min = index;}}}public int top() {return stack.peek();}public int getMin() {return min;}}每次在push和pop的时候求出最大值，很显然，pop的过程比较复杂，需要遍历整个栈，直接就超时。之后灵机一动，每次在push的时候，在搞一个栈把当前的最小值也push进去，如下代码：

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

结果直接内存爆掉，可想而知，每次push，都会同时push最小值，相当于栈的空间是以前的两倍。但是可以做下优化，并不是push的时候push两次，而是在最小值发生变化的时候在push。这样会节省不少空间。上代码

class MinStack {LinkedList<Integer> stack = new LinkedList<Integer>();LinkedList<Integer> minStack = new LinkedList<Integer>();int min = Integer.MAX_VALUE;public void push(int x) {stack.push(x);if (min >= x) {min = x;minStack.push(min);}}public void pop() {if (min == stack.peek()) {minStack.pop();if (minStack.isEmpty()) {min = Integer.MAX_VALUE;} else {min = minStack.peek();}}stack.pop();}public int top() {return stack.peek();}public int getMin() {return min;}}终于AC了！但是问题可以进一步探究，为什么存储的时候，不是把栈的差值存储呢？上代码：

LinkedList<Long> stack = new LinkedList<>();long min = Integer.MAX_VALUE;public void push(int x) {if (stack.isEmpty()) {stack.push(0L);min = x;} else {stack.push(x-min);if (x < min) {min = x;}}}public void pop() {long pop = stack.pop();if (pop < 0) {min -= pop;}}public int top() {long top = stack.peek();if (top > 0) {return (int) (top+min);} else {return (int) min;}}public int getMin() {return (int) min;}运行效率最好的方法！！！

，别想一下造出大海，必须先由小河川开始。