亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

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

系統(tǒng) 2097 0

要求

定義棧的數(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ù)的棧


更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號(hào)聯(lián)系: 360901061

您的支持是博主寫作最大的動(dòng)力,如果您喜歡我的文章,感覺我的文章對(duì)您有幫助,請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點(diǎn)擊下面給點(diǎn)支持吧,站長(zhǎng)非常感激您!手機(jī)微信長(zhǎng)按不能支付解決辦法:請(qǐng)將微信支付二維碼保存到相冊(cè),切換到微信,然后點(diǎn)擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對(duì)您有幫助就好】

您的支持是博主寫作最大的動(dòng)力,如果您喜歡我的文章,感覺我的文章對(duì)您有幫助,請(qǐng)用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長(zhǎng)會(huì)非常 感謝您的哦!!!

發(fā)表我的評(píng)論
最新評(píng)論 總共0條評(píng)論
主站蜘蛛池模板: 一级毛片a女人刺激视频免费 | 国产精品视频不卡 | 成 人 黄 色 | 一级毛片一级毛片a毛片欧美 | 一级a美女毛片 | 99久久99这里只有免费的精品 | 国产在线小视频 | 热久久久久久久 | 天天做日日做 | 九九99热久久国产 | 天天摸天天操免费播放小视频 | 国产操比 | 国产激情一区二区三区在线观看 | 成人a毛片手机免费播放 | 精品999久久久久久中文字幕 | 四虎精品永久在线网址 | 欧美成人免费xxx大片 | 人人草人人干 | 四虎影视成人永久在线观看 | 国产欧美久久久精品影院 | 免费观看成人碰视频公开 | 久久精品麻豆 | 五月婷婷在线视频观看 | 黄色四虎影院 | 四虎影视永久在线观看 | 国产日韩一区 | 四虎影视在线观看 | 国产激情小视频 | 欧美一级高清免费a | 亚洲精品亚洲人成在线播放 | 欧美日韩中文亚洲v在线综合 | 久久久久久综合成人精品 | 欧美日韩永久久一区二区三区 | 91精品久久久久久久久网影视 | 一级在线免费视频 | 日本精品中文字幕在线不卡 | 国产精品激情综合久久 | 亚洲国产一 | 国产亚洲精品在天天在线麻豆 | 色狠狠一区二区三区香蕉蜜桃 | 亚洲综合涩|