搜索

调用 min、push 及 pop 的时间复杂度都是 O(1)


因此实现一个能够得到栈的最小元素的 min 函数,我们就不能使用for等循环去查找,直接去排序大可不必,所以我们可以通过创建另一个栈,专门去存储每次比较的最小值。

新建两个栈数据结构,stack<int> s;stack<int> sort;

实现push加入函数,s就正常加,而sort里加每次比较后的最小值,最小值依旧在栈顶。

    void push(int x) {
        s.push(x);
        if(!sort.empty()){
            int num = sort.top()<x?sort.top():x;
            sort.push(num);
        }else{
            sort.push(x);
        }
    }

pop删除函数也有需要注意的地方

情况一:

sort和s栈顶元素都是最小值

我们一旦删除了s中的最小值,那么sort这个栈顶元素本身不存在了,为了做出同步,所以两个栈都需要删除。

情况二:

sort是最小值,s栈顶是非最小值,会不会有错误呢?

我们以,-2,0,-3,4压入为例,
如果我们同步删除两个栈的栈顶,-3被删除了,4被删除了,貌似最小值被我们删除了,可是你别忘记我们所写的push,最小值不止存入了一次,压入4之前,sort栈顶元素是-3,压入4时,4大于-3,因此,又一个-3被压入,删的只是本次比较的-3,之前的-3还是在栈中,不要忘记sort压入的是每次比较后的最小值,不是只有一个。

top函数不用多说,直接返回s的栈顶,min函数的实现方式则是返回sort的栈顶,sort栈顶永远是最小值。

完整代码

class MinStack {
public:
    stack<int> s;
    stack<int> sort;
    /** initialize your data structure here. */
    MinStack() {

    }
    
    void push(int x) {
        s.push(x);
        if(!sort.empty()){
            int num = sort.top()<x?sort.top():x;
            sort.push(num);
        }else{
            sort.push(x);
        }
    }
    
    void pop() {
        s.pop();
        sort.pop();
    }
    
    int top() {
        return s.top();
    }
    
    int min() {
        return sort.top();
    }
};

版权属于:染念
作品采用:本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可。
4
查看目录

目录

来自 《LeetCode155|剑指 Offer 30. 包含 min 函数的栈》
评论

博主很懒,啥都没有