例题分析--Min Stack

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

• push(x) -- Push element x onto stack.
• pop() -- Removes the element on top of the stack.
• top() -- Get the top element.
• getMin() -- Retrieve the minimum element in the stack.

-----------------------------

分析：

    >> 栈的性质：只能从最上面开始取出值，那么最小值也是要实时更新的

    >> 另外一个问题就是栈中的值可能是会有重复的

解决思路：   

    >> 使用两个栈，一个就是存储实际的数据，另外一个栈存储最小值，当然是不同时刻的最小值了，给数据栈压入数据时，先判断是否比当前最小值小，如果小于等于的话就同时压入最小值栈，弹出也是一样的了。

------------------------------

代码：

public class MinStack {
   private ArrayList data;
   private ArrayList minData;
   public MinStack() {
       data = new ArrayList();
       minData = new ArrayList();
   }
   public void push(int x) {
        // store current min value into minStack
        data.add(x);
        if (minData.size() == 0 || minData.get(minData.size() - 1) >= x) {
            minData.add(x);
        }
    }
    public void pop() {
        // use equals to compare the value of two object, if equal, pop both of them
        int temp1 = data.get(data.size() - 1), temp2 = minData.get(minData.size() - 1);
        if (temp1 == temp2) {
            minData.remove(minData.size() - 1);
        }
        data.remove(data.size() - 1);
    }
    public int top() {
        if (data.size() < 1) return -1;
            return data.get(data.size() - 1);
    }
    public int getMin() {
        return minData.get(minData.size() - 1);
    }
}