题目

题目来源：力扣（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]

思路分析

  1. 从队列尾部插入元素时，我们可以提前取出队列中所有比这个元素小的元素，使得队列中只保留对结 果有影响的数字。这样的方法等价于要求维持队列单调递减，即要保证每个元素的前面都没有比它小的元素。

  2. 我们只需要在插入每一个元素 value 时，从队列尾部依次取出比当前元素 value 小的元素，直到遇到 一个比当前元素大的元素 value’ 即可。

  3. 上面的过程需要从队列尾部取出元素，因此需要使用双端队列来实现。另外我们也需要一个辅助队列 来记录所有被插入的值，以确定 pop_front 函数的返回值。

  4. 保证了队列单调递减后，求最大值时只需要直接取双端队列中的第一项即可。

  1. var MaxQueue = function() {
  2.   // 记录所有被插入的值
  3.   this.queue1 = [];
  4.   // 维护一个值始终递减的队列
  5.   this.queue2 = [];
  6. };
  8. /**
  9.  * @return {number}
  10.  */
  11. MaxQueue.prototype.max_value = function() {
  12.   if (this.queue2.length) {
  13.     // 维护了一个递减的队列，队首元素就是队列中最大的元素
  14.     return this.queue2[0];
  15.   }
  17.   return -1;
  18. };
  20. /** 
  21.  * @param {number} value
  22.  * @return {void}
  23.  */
  24. MaxQueue.prototype.push_back = function(value) {
  25.  this.queue1.push(value);
  26. // 在插入每一个元素 value 时，从队列尾部依次取出比当前元素 value 小的元素，直到遇到一个比当前元素value大的元素
  27.  while (this.queue2.length && this.queue2[this.queue2.length - 1] < value) {
  28.    this.queue2.pop();
  29.  }
  30.  this.queue2.push(value);
  31. };
  33. /**
  34.  * @return {number}
  35.  */
  36. MaxQueue.prototype.pop_front = function() {
  37.   if (!this.queue1.length) {
  38.     return -1;
  39.   }
  41.   const value = this.queue1.shift();
  42.   if (value === this.queue2[0]) {
  43.     this.queue2.shift();
  44.   }
  46.   return value;
  48. };
  50. /**
  51.  * Your MaxQueue object will be instantiated and called as such:
  52.  * var obj = new MaxQueue()
  53.  * var param_1 = obj.max_value()
  54.  * obj.push_back(value)
  55.  * var param_3 = obj.pop_front()
  56.  */