最小栈

设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。

push(x) -- 将元素 x 推入栈中。

pop() -- 删除栈顶的元素。

top() -- 获取栈顶元素。

getMin() -- 检索栈中的最小元素。

示例:

MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin();   --> 返回 -3. minStack.pop(); minStack.top();     --> 返回 0. minStack.getMin();   --> 返回 -2.

我的思路

思路一

因为常数时间内检索到最小元素的栈的要求，我们需要记录最小元素。而考虑到这个最小元素有可能被删除，所以这里需要考虑给一个辅助集合。我看网上有一些使用栈的方法，但其实极容易出错，假设放的值大小就在是整个集合的中间位置，那是很难处理的事情。

我本来考虑使用的是LinkList，考虑原因是存放都比较多，而且本身这个List肯定是有序的，查起来次数会少些。但没想到，这种情况依旧过不了。换成ArrayList才能过，果然还是ArrayList强，以后我要基本都用ArrayList了。

class MinStack {    private Stack<Integer> stack;    private ArrayList<Integer> minList; ​    /** initialize your data structure here. */    public MinStack() {        stack = new Stack<>();        minList = new ArrayList<>();   } ​    public void push(int x) {        this.stack.push(x);        int minListSize = minList.size();        if(minListSize==0){            minList.add(x);            return;       }        if(minList.get(minListSize-1)<=x){            minList.add(x);            return;       }        for(int i = 0 ; i < minListSize;i++){            if(minList.get(i)>x){                minList.add(i,x);                break;           }       } ​   } ​    public void pop() {        Integer peek = this.stack.peek();        int minListSize = minList.size();        for(int i = 0 ; i < minListSize;i++){            if(minList.get(i).equals(peek)){                minList.remove(i);                break;           }       }        this.stack.pop();   } ​    public int top() {        return this.stack.peek();   } ​    public int getMin() {        return minList.get(0);   } }