首页 > 其他 > 详细

包含min函数的栈

时间:2019-07-24 11:58:59      阅读:100      评论:0      收藏:0      [点我收藏+]

题目描述

定义栈的数据结构,请在该类型中实现一个能够得到栈中所含最小元素的min函数(时间复杂度应为O(1))。
 
思路:用到两个栈:一个栈1全部压,一个栈2压入一个元素后,之后压的元素只能比之前的小于或者等于,这样一来最小的就是在栈2的栈顶,出栈的时候只有当栈1的栈顶元素和栈2的栈顶元素相同时,此时栈2出栈,最小的还是栈2的栈顶元素。
c++代码如下:
class Solution {
public:
     
    stack<int> stack1,stack2;
     
    void push(int value) {
        stack1.push(value);
        if(stack2.empty())
            stack2.push(value);
        else if(value<=stack2.top())
        {
            stack2.push(value);
        }
    }
     
    void pop() {
        if(stack1.top()==stack2.top())
            stack2.pop();
        stack1.pop();
         
    }
     
    int top() {
        return stack1.top();       
    }
     
    int min() {
        return stack2.top();
    }
     
};

 

包含min函数的栈

原文:https://www.cnblogs.com/cstdio1/p/11237051.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!