[239] 滑动窗口最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

示例 1：

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3

输出：[3,3,5,5,6,7]

解释：

滑动窗口的位置 最大值

---

[1 3 -1] -3 5 3 6 7 3

⁠1 [3 -1 -3] 5 3 6 7 3

⁠1 3 [-1 -3 5] 3 6 7 5

⁠1 3 -1 [-3 5 3] 6 7 5

⁠1 3 -1 -3 [5 3 6] 7 6

⁠1 3 -1 -3 5 [3 6 7] 7

示例 2：

输入：nums = [1], k = 1

输出：[1]

提示：

1 <= nums.length <= 10^5

-10^4 <= nums[i] <= 10^4

1 <= k <= nums.length

这里需要用到一个新的数据结构：单调队列。

由于滑动窗口不断滑动，若需要每次遍历都在 O(1) 的时间内知道最大值，则需要根据当前滑动窗口，维护一个单调递减的队列。

1. 每次滑动窗口加入新值时，触发单调队列的 push 操作。将队列中比当前值小的值全部去除，最后将该值送入队列，以维持队列单调递减。

2. 此时，由于队列单调递减，则滑动窗口中元素的最大值一定是单调队列的队头元素。此时单调队列的 getMax 操作即返回 queue[0]。

3. 滑动窗口的左侧移出时，触发单调队列的 pop 操作。判断单调队列的队头元素是否等于移出值，因为有可能在之前的 push 过程中被移除了。如果是则将单调队列中的队头移出，否则不作处理。

function maxSlidingWindow(nums: number[], k: number): number[] {
  if (nums.length == 0 || k == 0) return [];
  const dequeue = [];
  const res: number[] = [];
  // 初始化窗口
  for (let i = 0; i < k; i++) {
    // 保持单调队列的单调递减
    while (dequeue.length !== 0 && dequeue[dequeue.length - 1] < nums[i]) {
      dequeue.pop();
    }
    // 加入窗口右边界的值
    dequeue.push(nums[i]);
  }
  // 由于滑动窗口中元素单调递减，队头一定是当前滑动窗口的最大值
  res.push(dequeue[0]);

  for (let i = k; i < nums.length; i++) {
    // i - k 为窗口的左边界
    const left = i - k;
    // 如果这个元素在单调队列中，则直接删除
    if (dequeue[0] === nums[left]) {
      dequeue.shift();
    }

    // 保持单调队列的单调递减
    while (dequeue.length !== 0 && dequeue[dequeue.length - 1] < nums[i]) {
      dequeue.pop();
    }
    dequeue.push(nums[i]);

    res.push(dequeue[0]);
  }
  return res;
}