题目描述
剑指 Offer 59 - II. 队列的最大值 - 力扣（LeetCode）
python中的队列
- queue包
- 利用queue这个包，它不仅仅是实现了队列的逻辑结构，还实现了线程所需的锁定语义，特别适用于线程调度。
- queue包含Queue类、LifoQueue类、PriorityQueue类和SimpleQueue类。
- Queue：FIFO，普通队列，初始化设置队列长度，达到队列长度后再插入会阻塞，当设置长度≤0时，队列长度为无穷大。
- LifoQueue：LIFO，类似栈，初始化设置队列长度···ditto
- PriorityQueue：优先级队列，类似堆，初始化设置队列长度···ditto，可以根据sorted(list(entries))确定队列中每个entry的(priority_number, data)的最小值。
- SimpleQueue：FIFO，无边界队列。
- 双端队列：deque容器
- 调用
from collections import deque即可得到双端队列deque，是double-ended queue的简称，支持线程安全。
- 调用
解题思路
在原本的那个队列queue之余，再加一个长度更小的辅助队列，这个辅助是双端队列，时刻保持着对max和次max和次次max等等这样一个顺序的记录，具体方法是使用一个双端队列deque，在每次入队时，如果deque队尾元素小于即将入队的元素value，则将小于value的元素全部出队后，再将value入队；否则直接入队。
该辅助队列维护的是某状态时的峰值，比如辅助队列的队头第一个元素代表初始状态时（即所有队列元素中）的峰值、第二个元素代表从出队第一个元素之后并在出队当前第二个元素之前的峰值。
当queue中的元素出队时，考察该值是否和deque中的队首元素相同，若相同则说明此时输出的是个最大值，需要把deque中的队首元素一起取出，若不相同则说明此时输出的是个无关紧要的数，也就不需要更新deque，如此即可保证，deque的队首始终是queue的最大值。
Comments | NOTHING