题目链接

LeetCode

题目描述

请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。
若队列为空，pop_front 和 max_value 需要返回 -1

示例

示例 1：
输入: 
["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
[[],[1],[2],[],[],[]]
输出: [null,null,null,2,1,2]
示例 2：
输入: 
["MaxQueue","pop_front","max_value"]
[[],[],[]]
输出: [null,-1,-1]

解题思路

方法一：暴力方法

算法步骤如下：

• 枚举每个窗口的左边界 i
• 根据窗口的左边界i可以对应计算出右边界j

• 遍历窗口，计算出最大值 ```cpp class MaxQueue { public: vector v; MaxQueue() {

  }

  int max_value() {

    if(v.empty())
        return -1;
    int max = v[0];
    for(int i = 0;i<v.size();++i){
        if(v[i]>max)
            max = v[i];
    }
    return max;

  }

  void push_back(int value) {

    v.push_back(value);
  

  }

  int pop_front() {

    if(v.empty()){
        return -1;
    }
    int ret  = v[0];
    v.erase(v.begin());
    return ret;
  

  } };

/**

• Your MaxQueue object will be instantiated and called as such:
• MaxQueue* obj = new MaxQueue();
• int param_1 = obj->max_value();
• obj->push_back(value);
• int param_3 = obj->pop_front(); */ ```

• 时间复杂度：O(1)（插入，删除），O(n)（求最大值）。插入与删除只需要普通的队列操作，为 O(1)，求最大值需要遍历当前的整个队列，最坏情况下为 O(n))。
• 空间复杂度：O(n)需要用队列存储所有插入的元素。

方法二：单调队列

为了解决上述问题，我们只需记住当前最大值出队后，队列里的下一个最大值即可。

具体方法是使用一个双端队列 deque，在每次入队时，如果 deque 队尾元素小于即将入队的元素 value，则将小于 value 的元素全部出队后，再将 value 入队；否则直接入队。
这时，辅助队列 deque 队首元素就是队列的最大值。

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

    }

    int max_value() {
        if(dq.empty())
            return -1;
        return dq.front();
    }

    void push_back(int value) {
        q.push(value);
        while(!dq.empty()&&dq.back()<value)
            dq.pop_back();
        dq.push_back(value);
    }

    int pop_front() {
        if(q.empty())
            return -1;
        int ret = q.front();
        q.pop();
        if(ret==dq.front())
            dq.pop_front();
        return ret;
    }
};

/**
 * Your MaxQueue object will be instantiated and called as such:
 * MaxQueue* obj = new MaxQueue();
 * int param_1 = obj->max_value();
 * obj->push_back(value);
 * int param_3 = obj->pop_front();
 */

class MaxQueue {
    private Deque<Integer> queue, stack;
    public MaxQueue() {
        queue = new LinkedList<Integer>();
        stack = new LinkedList<Integer>();
    }

    public int max_value() {
        return stack.isEmpty() ? -1 : stack.peekFirst();
    }

    public void push_back(int value) {
        queue.offerLast(value);
        while(!stack.isEmpty() && stack.peekLast() < value){
            stack.pollLast();
        }
        stack.offerLast(value);
    }

    public int pop_front() {
        if(queue.isEmpty()){
            return -1;
        }
        int res = queue.pollFirst();
        if(!stack.isEmpty() && res == stack.peekFirst()){
            stack.pollFirst();
        }
        return res;
    }
}

/**
 * Your MaxQueue object will be instantiated and called as such:
 * MaxQueue obj = new MaxQueue();
 * int param_1 = obj.max_value();
 * obj.push_back(value);
 * int param_3 = obj.pop_front();
 */

时间复杂度

• max_value：O(1)，直接返回双端队列（或数组）头部的元素。
• pop_front：O(1)，从队列中弹出一个元素，仍然是常数时间复杂度。
• push_back：O(1)，例如 543216，只有最后一次 push_back 操作是O(n)，其他每次操作的时间复杂度都是 O(1)，均摊时间复杂度为(O(1)×(n−1)+O(n))/n=O(1)。