美文网首页
剑指offer-包含min函数的栈

剑指offer-包含min函数的栈

作者: yyming | 来源:发表于2019-02-23 09:33 被阅读0次

    题目定义栈的数据结构,请在该类型中实现一个能够得到栈中所含最小元素的min函数(时间复杂度应为O(1))。
    难点和坑点
    1.使用两个栈实现min函数的同时满足复杂度
    2.注意在有pop操作并且需要条件判断时注意先判断操作然后在pop操作
    3.在进行入栈操作时因为要判断value是否是最小值,如果是最小值就要同时入第二个栈,在由于我们是将value和第二个栈的栈顶元素比较,当第二个栈初试为空时比较失败会导致溢出等error,所以在push操作时要先判断第二个栈是否为空并进行复制操作;

    class Solution {
    public:
        stack<int> stack1,stack2;
        void push(int value) {
            stack1.push(value);
            if(stack2.empty())
                stack2.push(value);
            else if(stack2.top() >= value)
                stack2.push(value);
        }
        void pop() {
            if(stack1.top()==stack2.top())
                stack2.pop();
            stack1.pop();
        }
        int top() {
            return stack1.top();
        }
        int min() {
            return stack2.top();
        }
    };
    

    相关文章

      网友评论

          本文标题:剑指offer-包含min函数的栈

          本文链接:https://www.haomeiwen.com/subject/kvuuyqtx.html