LCR184.设计自助结算系统

链接：LCR184.设计自助结算系统
难度：Medium
标签：设计、队列、单调队列
简介：请定义一个队列并实现函数 max_value 得到队列里的最大值。

题解 1 - typescript

• 编辑时间：2021-07-20
• 执行用时：200ms
• 内存消耗：48.3MB
• 编程语言：typescript
• 解法介绍：单调递减队列。

class MaxQueue {
  private queue: number[] = [];
  private monoQueue: number[] = [];
  max_value(): number {
    if (this.queue.length === 0) return -1;
    return this.queue[this.monoQueue[0]];
  }
  push_back(value: number): void {
    this.queue.push(value);
    while (this.monoQueue.length && this.queue[this.monoQueue[this.monoQueue.length - 1]] < value)
      this.monoQueue.pop();
    this.monoQueue.push(this.queue.length - 1);
  }
  pop_front(): number {
    if (this.queue.length === 0) return -1;
    const v = this.queue.shift()!;
    for (let i = 0, n = this.monoQueue.length; i < n; i++) this.monoQueue[i]--;
    if (this.monoQueue[0] === -1) this.monoQueue.shift();
    return v;
  }
}