[Leetcode][Algo]155. Min Stack

这道题目跟之前那个MAX stack是一毛一样的。

从去年10月份自己写过一会以后前两天都没有重写一遍。今天按照之前的思路写了一下这个min stack，发现思路上出现很多问题。

1. 试图用min_value 作为最小值是否被弹出的依据。这样总是出错，最小值有可能不唯一。好比说栈里面有多个相等的最小值。

2. 记录上一个最小的index思维混乱了。应该要建立一个数组：

link2NextMinValue[], 里面的index-索引，应该是当前插入元素在栈内位置，也就是说这个数组应该是和栈数组同步增长的。

而这个数组的内容，应该是上一个最小值的index。如果该位置元素不是最小值，就赋值为-1.

然后一直保存一个局部变量，是当前最小值的index。

3. 每次弹出的时候，只要判断当前栈顶是否是最小index，如果是，就把当前的最小值index更新成link2NextMinValue[]里存的前一个最小值index就可以。

4. 用数组实现栈，其实操作数组的下标。pop操作，并不会真的删除。但是如果pop后重新写入了，那个原来的元素会被覆盖。

5. 还有一个边界值的问题。

minValue的默认值是INT_MAX

如果第一个入队的就是INT_MAX, 高亮的判断条件如果是"<" 不是"<="的话，minValueIndex就不会被赋值，就是-1，那么后面再用这个作为index取最小值的时候就会出错

 void push(int x) {

        stackValue[++stackTop] = x;
        if(x <= minValue()){
            link2NextMinValue[stackTop] = minValueIndex;
            minValueIndex = stackTop;
        }
        else
            link2NextMinValue[stackTop] = -1;
    }

    int minValue(){
        if(minValueIndex >= 0){
            return stackValue[minValueIndex]; //返回当前最大值
        }
        else{
            return INT_MAX;
        }
    }