要求

定義棧的數(shù)據(jù)結(jié)構(gòu)，要求添加一個(gè)min 函數(shù)，能夠得到棧的最小元素。?

要求函數(shù)min、push 以及pop 的時(shí)間復(fù)雜度都是O(1)。

解法1：

?

使用一個(gè)輔助棧來保存最小元素，這個(gè)解法簡(jiǎn)單不失優(yōu)雅。設(shè)該輔助棧名字為minimum stack，其棧頂元素為當(dāng)前棧中的最小元素。這意味著

?

• 要獲取當(dāng)前棧中最小元素，只需要返回minimum stack的棧頂元素即可。
• 每次執(zhí)行push操作，檢查push的元素是否小于或等于minimum stack棧頂元素。如果是，則也push該元素到minimum?stack中。
• 當(dāng)執(zhí)行pop操作的時(shí)候，檢查pop的元素是否與當(dāng)前最小值相等。如果相同，則需要將改元素從minimum?stack中pop出去。

    struct minStack{

    stack<int> s;

    stack<int> minS;



    void push(int i){

        if (s.empty() || minS.empty()){

            s.push(i);

            minS.push(i);

        }else{

            if (minS.top() >= i){

                minS.push(i);

            }

            s.push(i);

        }

    }



    void pop(){

        if (s.empty() || minS.empty()){

            return;

        }

        if (s.top() > minS.top()){

            s.pop();

        }else{

            s.pop();

            minS.pop();

        }

    }



    int min(){

        if (minS.empty())

            return -1;

        else 

            return minS.top();

    }

};


  

?

2.巧妙解法

?

另外一種解法利用存儲(chǔ)差值而不需要輔助棧，方法比較巧妙。其中需要說明的幾點(diǎn)：

push(int elem)函數(shù)在棧中壓入當(dāng)前元素與當(dāng)前棧中最小元素的差值，然后通過比較當(dāng)前元素與當(dāng)前棧中最小元素大小，并將它們中間的較小值壓入。

pop()函數(shù)執(zhí)行的時(shí)候，先pop出棧頂?shù)膬蓚€(gè)值，這兩個(gè)值分別是當(dāng)前棧中最小值min和最后壓入的元素與棧中最小值的差值diff。如果diff<0，則表示最后壓入棧的元素是最小的元素，因此只需將min-diff壓入棧中，并將min值返回即可。min-diff就是當(dāng)前元素彈出后，棧中剩下元素的最小值。而如果diff>=0且棧不為空，則表示當(dāng)前值不是最小值，所以需要在棧中壓入最小值min并將diff+min返回；如果棧為空，則表示已經(jīng)是最后一個(gè)數(shù)字，直接返回min即可。

?

    struct minStackLessSpace{

    

    void push(int i){

        if (s.empty()){

            s.push(i);

            s.push(i);

        }

        if (i - s.top() < 0){

            s.pop();

            s.push(i-s.top());

            s.push(i);

        }else{

            int j = s.top();

            s.pop();

            s.push(i);

            s.push(j);

        }

    }



    bool pop(){

        if (s.empty())

            return false;

        int i = s.top();

        s.pop();

        if (s.top() < 0){

            int j = s.top();

            s.pop();

            s.push(i - j);

        }else{

            s.pop();

            s.push(i);

        }

    }

    

    stack<int> s;

};
  

參考：

?

http://blog.csdn.net/ssjhust123/article/details/7752878

設(shè)計(jì)包含min函數(shù)的棧