# \[剑指Offer-59-II]\[中等]\[滑动窗口] 队列的最大值

## 题目描述

[剑指 Offer 59 - II. 队列的最大值](https://leetcode-cn.com/problems/dui-lie-de-zui-da-zhi-lcof/)

请定义一个队列并实现函数 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]
```

限制：

* 1 <= push\_back,pop\_front,max\_value的总操作数 <= 10000
* 1 <= value <= 10^5

## 解题思路

使用一个辅组队列, 保存队列的头部是当前真正队列中的最大值. 具体方法参考[\[239\]\[困难\]\[队列\] 滑动窗口最大值](https://kerasnoone.gitbook.io/garnet/suan-fa/dui-lie/broken-reference).

```python
class MaxQueue:

    def __init__(self):
        self.queue = deque()
        self.max_queue = []

    def max_value(self) -> int:
        return self.max_queue[0] if self.max_queue else -1

    def push_back(self, value: int) -> None:
        self.queue.append(value)
        while self.max_queue and self.max_queue[-1] < value:
            self.max_queue.pop()
        self.max_queue.append(value)

    def pop_front(self) -> int:
        if not self.queue:
            return -1
        value = self.queue.popleft()
        if self.max_queue and self.max_queue[0] == value:
            self.max_queue.pop(0)
        return value


# Your MaxQueue object will be instantiated and called as such:
# obj = MaxQueue()
# param_1 = obj.max_value()
# obj.push_back(value)
# param_3 = obj.pop_front()
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://kerasnoone.gitbook.io/garnet/suan-fa/dui-lie/jian-zhi-offer59ii-dui-lie-de-zui-da-zhi.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.