• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            posts - 183,  comments - 10,  trackbacks - 0
            設(shè)計(jì)一個(gè)保護(hù) min 函數(shù)的棧,min 函數(shù)返回棧的最小元素。并且 min、push、pop 函數(shù)的時(shí)間復(fù)雜度都為 O(1)。

            主要思想是定義一個(gè)輔助棧記錄最小元素在原棧中的索引。

            實(shí)現(xiàn)中參考:
            http://hi.baidu.com/xiangzifengshi/blog/item/2f9e833aef17d6f7828b131e.html
            http://zhedahht.blog.163.com/blog/static/25411174200712895228171/

            代碼實(shí)現(xiàn):
             1 #include <iostream>
             2 #include <ctime>
             3 #include <cassert>
             4 using namespace std;
             5 
             6 class MinStack
             7 {
             8 private:
             9     int stack[100];
            10     int p;
            11     int minstack[100];
            12     int q;
            13     
            14     bool minEmpty()
            15     {
            16         return q == 0;
            17     }
            18     void minPop()
            19     {
            20         assert(!minEmpty());
            21         --q;
            22     }
            23     int minTop()
            24     {
            25         assert(!minEmpty());
            26         return minstack[q - 1];
            27     }
            28 public:
            29     MinStack() : p(0), q(0) {}
            30     bool empty()
            31     {
            32         return p == 0;
            33     }
            34     void push(int i)
            35     {
            36         stack[p++= i;
            37         if (minEmpty())
            38         {
            39             minstack[q++= p - 1;
            40         }
            41         else
            42         {
            43             if (i <= stack[minTop()])
            44             {
            45                 minstack[q++= p - 1;
            46             }
            47         }
            48     }
            49     void pop()
            50     {
            51         assert(!empty());
            52         if (top() == stack[minTop()])
            53         {
            54             minPop();
            55         }
            56         --p;
            57     }
            58     int min()
            59     {
            60         assert(!empty());
            61         return stack[minTop()];
            62     }
            63     int top()
            64     {
            65         assert(!empty());
            66         return stack[p - 1];
            67     }
            68 };
            69 
            70 int main()
            71 {
            72     MinStack ms;
            73     srand(time(0));
            74     for (int i = 0; i < 10++i)
            75     {
            76         int n = rand() % 100;
            77         ms.push(n);
            78     }
            79     while (!ms.empty())
            80     {
            81         cout << ms.top() << '\t' << ms.min() << endl;
            82         ms.pop();
            83     }
            84     return 0;
            85 }
            posted on 2011-04-23 01:28 unixfy 閱讀(164) 評(píng)論(0)  編輯 收藏 引用

            只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
            網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問   Chat2DB   管理


            国产精品久久久久蜜芽| 久久久久久久综合日本亚洲 | 国内精品久久久久久野外| 久久久91人妻无码精品蜜桃HD| 久久久久高潮毛片免费全部播放| 久久亚洲国产成人影院| 久久人做人爽一区二区三区| 久久久久久人妻无码| 久久精品无码一区二区日韩AV| 国产精品乱码久久久久久软件| avtt天堂网久久精品| 中文精品久久久久国产网址| 波多野结衣久久精品| 99久久国产综合精品成人影院| 日韩乱码人妻无码中文字幕久久| 国产精品热久久毛片| 亚洲精品国精品久久99热一| 夜夜亚洲天天久久| 久久久久亚洲AV无码专区体验| 久久久久久免费视频| 91亚洲国产成人久久精品网址| 久久精品青青草原伊人| 国产精品免费久久久久电影网| 亚洲成色www久久网站夜月| 四虎国产精品免费久久久| 亚洲AV无码成人网站久久精品大| 亚洲伊人久久成综合人影院 | 久久精品国产亚洲一区二区三区 | 久久国产免费观看精品3| 亚洲国产天堂久久综合| 91久久精品国产成人久久| 久久精品99久久香蕉国产色戒 | 人妻无码αv中文字幕久久| 久久婷婷五月综合色99啪ak| 国产亚洲欧美精品久久久 | 久久精品成人欧美大片| 久久久久免费看成人影片| 亚洲国产欧洲综合997久久| 亚洲欧美伊人久久综合一区二区| 亚洲国产视频久久| 久久久亚洲AV波多野结衣|