239. Sliding Window Maximum

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function (nums, k) {
  // 时间复杂度是O(n^2) 考虑max的复杂度
  const n = nums.length
  const ans = []
  const window = nums.slice(0, k)
  for (let right = k; right < n + 1; right++) {
    ans.push(Math.max(...window))
    window.push(nums[right])
    window.splice(0, 1)
  }
  return ans
}

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function (nums, k) {
  // O(n) 单调队列
  const ans = []
  const q = new Deque() // datastructures-js/deque
  for (let i = 0; i < nums.length; i++) {
    // 1. 右入
    while (!q.isEmpty() && nums[q.back()] < nums[i]) {
      q.popBack() // 维护 q 的单调性
    }
    q.pushBack(i) // 注意保存的是下标，这样下面可以判断队首是否离开窗口

    // 2.左出
    const left = i - k + 1
    if (q.front() < left) {
      q.popFront()
    }

    // 3. 在窗口左端点处记录答案
    if (left >= 0) {
      // 由于队首到队尾单调递减，所以窗口最大值就在队首
      ans.push(nums[q.front()])
    }
  }

  return ans
}