单调队列：滑动窗口最大值

一、面试常考点

1. 单调队列维护规则

队尾弹出更小值，队头维护窗口内有效下标。

2. 与堆的对比

单调队列是 O(n)，堆通常 O(n log k)。

二、细节介绍

1. 入队

先弹出队尾比当前小的下标。

2. 出队

若队头已滑出窗口则弹出。

三、示例代码

function maxSlidingWindow(nums, k) {
  const deque = []
  const res = []

  for (let i = 0; i < nums.length; i++) {
    while (deque.length && nums[deque[deque.length - 1]] <= nums[i]) {
      deque.pop()
    }
    deque.push(i)

    if (deque[0] <= i - k) deque.shift()
    if (i >= k - 1) res.push(nums[deque[0]])
  }

  return res
}

四、常用应用场景

1. 实时监控

固定时间窗最大值/最小值。

2. 风控阈值检测

窗口峰值预警。