LeetCode-239.滑动窗口最大值

题目详解

相关链接

• 代码随想录

思路

• 暴力解法时间复杂度是 O(n^2)，而用单调队列只有 O(n)
  • 使用双端队列实现单调递减队列，队顶始终是最大值
  • 每次滑动窗口时，均有元素入队和出对，然后队顶元素就是当前窗口的最大值

看完代码随想录之后的想法

• 将单调队列的代码抽离封装好，主流程十分简单已读

实现过程中遇到的困难

• 实现单调队列时入队逻辑

代码

TypeScript

function maxSlidingWindow(nums: number[], k: number): number[] {
  const res: number[] = [],
    queue = new MonoQueue<number>()
  for (let i = 0; i < nums.length; i++) {
    queue.enqueue(nums[i])
    if (i >= k) queue.dequeue(nums[i - k])
    if (i >= k - 1) res.push(queue.top())
  }
  return res
}

/** 单调递减队列 */
class MonoQueue<T> {
  queue: T[]
  constructor() {
    this.queue = []
  }

  enqueue(value: T): void {
    // 比value小的都剔除
    while (this.queue.length && value > this.queue[this.queue.length - 1]) this.queue.pop()
    this.queue.push(value)
  }

  dequeue(value: T): void {
    // value可能在前面元素push的时候已经被剔除了
    if (value === this.top()) this.queue.shift()
  }

  top(): T {
    return this.queue[0]
  }
}

时间复杂度：O(n)
空间复杂度：O(n)

收获

• 学习了单调队列