剑指 Offer 59 - II. 队列的最大值｜刷题打卡

一、题目描述：

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

二、思路分析：

题目核心是实现一个最大值的队列，队列存在几种方法：最大值、入队、出队。

我们可以使用两个数组，一个存放正常的队列元素element，正常出队、入队；一个存放当前最大值maxQueue，根据元素队列的出入队做相应逻辑操作。

max_value

如果元素队列为空，返回-1；否则，最大值直接返回maxQueue的头部元素即可。

push_back

我们想要求队列的最大值，就需要在元素入队时进行比较。有几种情况需要考虑：

• maxQueue队列为空：直接push。
• maxQueue不为空：

• maxQueue的最后一位小于当前要插入的value，执行出栈操作，当最后一位大于或等于时停止出栈，将要插入的value再插入到maxQueue中。
• maxQueue的最后一位大于或等于当前要插入的value，直接将value插入到maxQueue中。

入队示例：

maxQueue.push_back(2);

maxQueue.push_back(4);

maxQueue.push_back(2);

maxQueue.push_back(1);

maxQueue.push_back(5);

pop_front

根据push方法，出队时，只需要考虑maxQueue[0]是否等于要出队的元素：等于则将maxQueue的头部出队；否则maxQueue就不需要任何操作。 入队示例：

maxQueue.push_back(4);

maxQueue.push_back(2);

maxQueue.push_back(1);

maxQueue.pop_front()  // 4

三、AC 代码：

class MaxQueue {
   element: number[];
  maxQueue: number[];
  constructor() {
    this.element = [];
    this.maxQueue = [];
  }
  max_value(): number {
    if (!this.element.length) return -1;
    return this.maxQueue[0];
  }
  push_back(value: number): void {
    this.element.push(value);
   while (this.maxQueue[this.maxQueue.length - 1] < value) {
      this.maxQueue.pop();
    }
    this.maxQueue.push(value);
  }
  pop_front(): number {
    if (!this.element.length) return -1;
    if (this.maxQueue[0] === this.element[0]) {
      this.maxQueue.shift();
    }
    return this.element.shift();
  }
}

四、总结：

需要掌握队列和栈的基本方法。在考虑入队时，需要十分明白最大队的头部最大的原则，并且需要考虑后入队的较小元素的执行情况。

作者：ClyingDeng

链接：https://juejin.cn/post/6950491187434225694

来源：稀土掘金

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。