设计包含min函数的栈

系统 1894 0

要求

定义栈的数据结构,要求添加一个min 函数,能够得到栈的最小元素。 

要求函数min、push 以及pop 的时间复杂度都是O(1)。


解法1:

 

使用一个辅助栈来保存最小元素,这个解法简单不失优雅。设该辅助栈名字为minimum stack,其栈顶元素为当前栈中的最小元素。这意味着

 

  • 要获取当前栈中最小元素,只需要返回minimum stack的栈顶元素即可。
  • 每次执行push操作,检查push的元素是否小于或等于minimum stack栈顶元素。如果是,则也push该元素到minimum stack中。
  • 当执行pop操作的时候,检查pop的元素是否与当前最小值相等。如果相同,则需要将改元素从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.巧妙解法

 

另外一种解法利用存储差值而不需要辅助栈,方法比较巧妙。其中需要说明的几点:

push(int elem)函数在栈中压入当前元素与当前栈中最小元素的差值,然后通过比较当前元素与当前栈中最小元素大小,并将它们中间的较小值压入。

pop()函数执行的时候,先pop出栈顶的两个值,这两个值分别是当前栈中最小值min和最后压入的元素与栈中最小值的差值diff。如果diff<0,则表示最后压入栈的元素是最小的元素,因此只需将min-diff压入栈中,并将min值返回即可。min-diff就是当前元素弹出后,栈中剩下元素的最小值。而如果diff>=0且栈不为空,则表示当前值不是最小值,所以需要在栈中压入最小值min并将diff+min返回;如果栈为空,则表示已经是最后一个数字,直接返回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


设计包含min函数的栈


更多文章、技术交流、商务合作、联系博主

微信扫码或搜索:z360901061

微信扫一扫加我为好友

QQ号联系: 360901061

您的支持是博主写作最大的动力,如果您喜欢我的文章,感觉我的文章对您有帮助,请用微信扫描下面二维码支持博主2元、5元、10元、20元等您想捐的金额吧,狠狠点击下面给点支持吧,站长非常感激您!手机微信长按不能支付解决办法:请将微信支付二维码保存到相册,切换到微信,然后点击微信右上角扫一扫功能,选择支付二维码完成支付。

【本文对您有帮助就好】

您的支持是博主写作最大的动力,如果您喜欢我的文章,感觉我的文章对您有帮助,请用微信扫描上面二维码支持博主2元、5元、10元、自定义金额等您想捐的金额吧,站长会非常 感谢您的哦!!!

发表我的评论
最新评论 总共0条评论