155. 最小栈

class MinStack {
    //通过数组模拟栈
    ArrayList<Integer> ls;
    //记录一段事件的最小值
    int min;
    // 指针指着最后一个位置
    int flag;
    // 通过贪心思想策略保存相对区域中的最小值 也就是最小栈
    ArrayList<Integer> mins;

    /** initialize your data structure here. */
    public MinStack() {
        ls = new ArrayList<Integer>();
        mins = new ArrayList<Integer>();
        //初始化是最大值
        min = Integer.MAX_VALUE;
        ls.add(0);
        mins.add(Integer.MAX_VALUE);
        flag = 0;
    }

    public void push(int x) {
        flag++;
        if (x < min)
            min = x;
        mins.add(min);
        ls.add(x);
    }

    public void pop() {
        ls.remove(flag);
        mins.remove(flag);
        // 可能最小值被移出来了 min需要变成 第二个最小值
        flag--;

        min = mins.get(flag);
    }

    public int top() {
        return ls.get(flag);
    }

    public int getMin() {
        return mins.get(flag);
    }
}