最小棧的實作

問題描述：

實作一個棧，帶有出棧（pop），入棧（push），取最小元素（getMin）三個方法。要保證這三個方法的時間複雜度都是O（1）。

問題分析：

假設存儲元素的棧為ms棧；

主要的難點在于擷取棧最小元素getMin()要保證其時間複雜度為O(1)；

而且由于存在push()和pop()操作，棧中最小元素currMin随時可能會因為入棧元和彈出操作而發生動态變化，是以需要一種機制，能夠時刻記錄目前棧的最小元素；

這裡，可以考慮用一個輔助棧aux，當ms棧的第一個元素入棧時，aux将第一個元素的索引0入棧；

那麼後續如何來保證aux的棧頂元素實時記錄着ms棧的最小元素的索引呢？

當入棧操作時，如果入棧元素小于目前棧中最小元素（aux棧頂元素所對應的元素），更新目前最小元素，并将新的最小元素的索引（也即是top值）入輔助棧；

當出棧操作時，如果出棧元素等于目前棧中最小元素，先将aux棧頂元素彈出，在更新目前最小元素；

如此操作可保證aux的棧頂元素實時記錄着ms棧目前元素的最小值。

實作：

package agother;
import java.util.ArrayList;
import java.util.Stack;
public class MinStack {

    private ArrayList<Integer> ms = new ArrayList<Integer>();//棧元素的存儲借助ArrayList
    private Stack<Integer> aux = new Stack<Integer>();//輔助的普通棧
    private int currMin = Integer.MAX_VALUE;//目前最小值
    private int top = -1;//棧頂指針
    public void push(int ele){
        ms.add(ele);
        top++;
        if (ele < currMin) {//如果入棧元素小于目前棧中最小與元素，更新目前最小元素，并将新的最小元素的位置（也即是top值）入輔助棧
            currMin = ele;
            aux.push(top);
        }
    }
    public Integer pop(){
        if (top<0) {return null;}
        Integer ele = ms.remove(top);
        top--;
        if (ele == currMin) {//如果出棧元素等于目前棧中最小元素，更新目前最小元素為次小元素，并彈出aux棧頂元素。
            aux.pop();
            currMin = ms.get(aux.peek());
        }
        return ele;
    }
    /*
     * 實際上，輔助棧的棧頂元素始終記錄的是ms棧中最小元素的索引值
     * 即是是在ms壓棧或者出棧的過程中，通過調整，任然保持着這一事實
     * 是以getMin()方法總能以O(1)的時間複雜度正确找到ms棧的最小元素
     * */
    public Integer getMin(){
        if (aux.isEmpty()) {
            return null;
        }else {
            return currMin;//或者傳回ms.get(aux.peek())
        }
    }
    public int size(){
        return top+1;
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        try {
            MinStack ms = new MinStack();
            ms.push(10);
            ms.push(3);
            ms.push(5);
            ms.push(15);
            ms.push(2);
            ms.push(8);
//            System.out.println(ms.size());
//            System.out.println(ms.getMin());
//            System.out.println(ms.pop());
//            System.out.println(ms.pop());
//            System.out.println(ms.pop());
//            System.out.println(ms.pop());
//            System.out.println(ms.pop());
            System.out.println(ms.getMin());
        } catch (Exception e) {
            // TODO: handle exception
            e.printStackTrace();
        }
    }

}      

轉載請注明原文位址：http://www.cnblogs.com/qcblog/p/7695988.html