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

为什么滑动窗口最大值要用单调队列而不是单调栈？

• 区别 (239): 窗口会从左侧移出元素, 需要"从两端都能删除"的结构;
• 选择: 用双端队列, 队尾做单调栈式的入队消除, 队头负责淘汰过期下标;
• 单调性: 维护单调递减队列, 队头始终是当前窗口最大值;

单调队列的三个动作是什么？

• 入队: 新元素从队尾进入前, 弹出队尾所有不大于它的元素, 保证递减;
• 过期: 队头下标小于 i - k + 1 时从队头移除, 即已滑出窗口;
• 取值: 窗口形成后, 每轮记录队头下标对应的值;

const maxSlidingWindow = (nums, k) => {
  const deque = [];
  const res = [];
  for (let i = 0; i < nums.length; i++) {
    while (deque.length && nums[deque.at(-1)] <= nums[i]) deque.pop();
    deque.push(i);
    if (deque[0] < i - k + 1) deque.shift();
    if (i >= k - 1) res.push(nums[deque[0]]);
  }
  return res;
};

• 时间 $O(n)$: 每个下标最多进队一次、出队一次;
• 空间 $O(k)$;