美文网首页
剑指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