🚩传送门：力扣题目

题目

请定义一个队列并实现函数 [LC]59. 队列的最大值 - 图1 得到队列里的最大值，要求函数 [LC]59. 队列的最大值 - 图2、 [LC]59. 队列的最大值 - 图3 和 [LC]59. 队列的最大值 - 图4 的均摊时间复杂度都是[LC]59. 队列的最大值 - 图5。

若队列为空，[LC]59. 队列的最大值 - 图6 和[LC]59. 队列的最大值 - 图7 需要返回 [LC]59. 队列的最大值 - 图8。

示例 1：

输入: [“MaxQueue”,”push_back”,”push_back”,”max_value”,”pop_front”,”max_value”][[],[1],[2],[],[],[]] 输出: [null,null,null,2,1,2]

解题思路：单调双端队列

如下图所示，考虑构建一个 递减列表 来保存队列 所有递减的元素 ，递减链表随着入队和出队操作实时更新，这样队列最大元素就始终对应递减列表的首元素，实现了获取最大值 [LC]59. 队列的最大值 - 图9 时间复杂度。
[LC]59. 队列的最大值 - 图10

复杂度分析

时间复杂度：[LC]59. 队列的最大值 - 图11，函数 [LC]59. 队列的最大值 - 图12、[LC]59. 队列的最大值 - 图13 和 [LC]59. 队列的最大值 - 图14 的均摊时间复杂度都是[LC]59. 队列的最大值 - 图15。

空间复杂度：[LC]59. 队列的最大值 - 图16，当元素个数为 [LC]59. 队列的最大值 - 图17 时，最差情况下 deque 中保存 [LC]59. 队列的最大值 - 图18 个元素；

我的代码

  1. class MaxQueue {
  2.     LinkedList<Integer> resQueue = null;
  3.     LinkedList<Integer> maxQueue = null;
  5.     public MaxQueue() {
  6.         resQueue = new LinkedList<>();
  7.         maxQueue = new LinkedList<>();
  8.     }
  10.     public int max_value() {
  11.         if (!maxQueue.isEmpty()) return maxQueue.peekFirst();
  12.         return -1;
  13.     }
  15.     public void push_back(int value) {
  16.         // resQueue添加当前值
  17.         resQueue.addLast(value);
  18.         if (maxQueue.isEmpty()) {
  19.             // 最大队列空,直接添加
  20.             maxQueue.addLast(value);
  21.         } else if (value > maxQueue.peekFirst()) {
  22.             // value大于最大值,直接清空,添加当前元素
  23.             maxQueue.clear();
  24.             maxQueue.addLast(value);
  25.         } else if (value < maxQueue.peekLast()) {
  26.             // 小于最小值
  27.             maxQueue.addLast(value);
  28.         } else {
  29.             // 移除中间值
  30.             while (!maxQueue.isEmpty() && maxQueue.peekLast() < value) {
  31.                 maxQueue.pollLast();
  32.             }
  33.             // maxQueue添加当前值
  34.             maxQueue.addLast(value);
  35.         }
  36.     }
  38.     public int pop_front() {
  39.         if (!resQueue.isEmpty()) {
  40.             int pop = resQueue.pollFirst();
  41.             if (maxQueue.peekFirst() == pop)
  42.                 maxQueue.pollFirst();
  43.             return pop;
  44.         }
  45.         return -1;
  46.     }
  48.     public static void main(String[] args) {
  49.         MaxQueue mq = new MaxQueue();
  51.     }
  52. }