• <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   管理


            精品久久久久成人码免费动漫| 久久精品一本到99热免费| 漂亮人妻被黑人久久精品| 久久精品国产久精国产果冻传媒| 欧美亚洲国产精品久久| 久久亚洲中文字幕精品一区| 亚洲精品无码久久久久久| 99久久国产综合精品麻豆| 久久亚洲国产午夜精品理论片| 99久久国产综合精品成人影院| 久久99亚洲综合精品首页| 亚洲精品99久久久久中文字幕| 少妇久久久久久久久久| 日韩精品国产自在久久现线拍| 久久久久亚洲av毛片大| 亚洲中文字幕无码一久久区| 久久免费视频网站| 色偷偷偷久久伊人大杳蕉| 久久久艹| 国产精品久久毛片完整版| 天天影视色香欲综合久久| 精品亚洲综合久久中文字幕| 欧美精品乱码99久久蜜桃| 97超级碰碰碰碰久久久久| 人妻无码αv中文字幕久久| 日日狠狠久久偷偷色综合96蜜桃| 97超级碰碰碰久久久久| 久久人做人爽一区二区三区| 7国产欧美日韩综合天堂中文久久久久 | 国产精品嫩草影院久久| 狠狠综合久久综合88亚洲| 99久久国产热无码精品免费久久久久 | 99热成人精品热久久669| 亚洲国产香蕉人人爽成AV片久久| 久久精品国产99国产电影网| 伊人久久无码中文字幕| 伊人伊成久久人综合网777| 精品国产91久久久久久久a| 久久精品无码一区二区三区| 亚洲国产另类久久久精品小说 | 欧美一级久久久久久久大|