[LeetCode]Min Stack，解题报告

目录题目

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

思路1

这道题算是面试过程中比较简单的题目，在实现基础栈的基础上，增加了一个在O(1)时间复杂度下获取当前栈内最小值的需求。 很自然的可以想到，可以用ArrayList来构建stack，同时用一个int类型的变量minIndex作为当前最小值的下标。

每次push(x)操作时，判断是否需要更新minIndex。每次pop操作时，判断当前移除的是否为minIndex，如果是，则需要O(n)时间复杂度更新minIndex。

思路有了，我们可以先写代码尝试一下，这种思路是否可以AC这道题目。

AC代码import java.util.ArrayList;{private ArrayList<Integer> stack = new ArrayList<Integer>();private int minIndex = 0;(int x) {stack.add(x);if (x < stack.get(minIndex) || stack.size() == 1) {minIndex = stack.size() – 1;}}() {if (minIndex == stack.size() – 1) {minIndex = 0;for (int i = 1; i < stack.size() – 1; i ++) {if (stack.get(i) < stack.get(minIndex)) {minIndex = i;}}}stack.remove(stack.size() – 1);}() {return stack.get(stack.size() – 1);}() {return stack.get(minIndex);}}缺陷

虽然上面的代码可以AC，而且getMin()方法的时间复杂度是O(1)，但是我们在pop方法中，当需要更新minIndex时，花费的时间复杂度是O(n)，严格的说，上面的代码是不符合面试要求的。 减少时间复杂度最便捷的方法就是增加空间复杂度，，很自然的我们想到“双栈法”。再维护一个最小数的栈，这样更新minIndex的操作我们可以通过最小数出栈的方式来搞定了。

思路2

双栈法的思路是：增加一个最小栈。当最小栈为空或者当前push元素小于等于最小栈栈顶元素时，该push元素也要push到最小栈中。

AC代码import java.util.Stack;{private Stack<Integer> normalStack = new Stack<Integer>();private Stack<Integer> minStack = new Stack<Integer>();(int x) {if (minStack.size() == 0 || x <= minStack.peek()) {minStack.push(x);}normalStack.push(x);}() {if (normalStack.peek().equals(minStack.peek())) {minStack.pop();}normalStack.pop();}() {return normalStack.peek();}() {return minStack.peek();}}

到尽头，也许快乐，或有时孤独，如果心在远方，