最大队列

最大队列

维护一个队列 X，X 中元素为 Q 中对应元素至队尾的最大值。此时 X 需要能从队尾出队。 可以只保存不同元素，X 中元素增加一个计数器，得到 Y。

• 入队时，若当前元素大于队尾元素，计数器累加上队尾元素的计数器，队尾元素出队，循环直至当前元素大于队尾元素，再将当前元素和计数器入队，若当前元素小于队尾元素，直接将当前元素入队。
• 出队时，若队首元素计数器大于 1，直接自减，若为 1，则出队。 均摊时间复杂度为 $O(1)$。