看起来挺简单，但是写起来才有坑。

模仿java里面的栈

1、用数组存放元素

2、设置size和index，push和pop只需要移动index就好了，不需要处理元素。

3、初始化为16，如果满了要扩容到2倍，为了偷懒，数组只增不减。

 

最后就是处理min的问题，原来想着提供一个min变量，每次插入的时候更新min即可。

但是如果刚好pop了一个min呢?上一个min是多少?

当然可以使用一个secondMin变量，但是连续pop两个呢？上上个呢？

所以使用变量不行。

因为只需要在获取的时候是常数，维护min不做限制，那么使用优先队列就好了。

注意在pop的时候，要注意pop的是不是最小值，是的话有限队列也要poll

 

没进行出错处理，比如pop到负数，但是题目本身也没这样的操作。过了

class MinStack {    int size;        int index;        //只有一个min，或者两个min，不能实现该功能        //如果pop了一个min，没法获取之前的最小值了        //使用最小堆就好了        PriorityQueue
     
       min;        int [] array;            /** initialize your data structure here. */            // 初始化给16            public MinStack() {                size = 16;                index = 0;                array = new int [16];                min = new PriorityQueue<>();            }            public void push(int x) {                //扩容                if(index==size-1){                    size*=2;                    int [] temp = new int [size];                    int ori = size/2;                    for(int i=0;i
     

 

 

 

排第一的答案很有趣！是自定义的数据结构来维护min值！

使用了一个栈来保存Pair

 

Pair是当前值val对应的min值

 

每次push的时候更新min值，然后创建Pair，压栈

 

因为用的是栈，就算是同一个数字，后入和先入的也能区分不同的min。

而且这个栈st和题目要求的栈刚好可以同步pop，也算巧妙吧！