剑指 Offer 59 - II 队列的最大值

概述

https://leetcode-cn.com/problems/dui-lie-de-zui-da-zhi-lcof/

有一道最大栈的题目和这个很像啊。

队列 + 双端队列

显然，当一个较大值进入队列后，以往比起小的值都没有了存在的意义。

class MaxQueue {
public:
    queue<int> q;
    deque<int> d;
    MaxQueue() {

    }
    
    int max_value() {
        if (!d.empty()) return d.front();
        return -1;
    }
    
    void push_back(int value) {
        q.push(value);
        while (!d.empty() && d.back() < value) d.pop_back();
        d.push_back(value);
    }
    
    int pop_front() {
        if (q.empty()) return -1;
        int v = q.front();
        q.pop();
        if (v == d.front()) {
            d.pop_front();
        }
        return v;
    }
};

Links: sword-offer-59-2

未经允许，禁止转载，本文源站链接：https://iamazing.cn/