2090. 半径为 k 的子数组平均值

题意

给你一个下标从 0 开始的数组 nums，以及一个整数 k。

下标 i 的 k 半径子数组平均值 指的是以 i 为中心、半径为 k 的子数组 nums[i - k] 到 nums[i + k] 的平均值。如果 i 左右两侧不足 k 个元素，则该位置的结果为 -1。

题目链接：2090. 半径为 k 的子数组平均值

思路

这道题仍然是固定长度滑动窗口。

以某个下标为中心，左右各取 k 个元素，所以窗口长度固定为：

const n = 2 * k + 1

当窗口右端来到 i 时，如果窗口长度已经达到 n，那么：

• 窗口左端是 left = i - n + 1；
• 窗口中心是 center = left + k；
• res[center] = Math.floor(sum / n)。

窗口未成形时不更新答案。每次更新后，再把左端元素移出窗口。

特殊情况：如果 k === 0，每个元素的半径子数组就是它自己，直接返回 nums。

代码

function getAverages(nums: number[], k: number): number[] {
  let res = nums.map((i) => -1)
  let sum = 0
  if (k === 0) {
    return nums
  }
  for (let i = 0; i < nums.length; i++) {
    // 入
    sum += nums[i]
 
    // 更新
    let n = 2 * k + 1 // 窗口长度
    let left = i - n + 1
    let center = left + k
    if (left < 0) {
      continue
    }
    res[center] = Math.floor(sum / n)
 
    // 出
    sum -= nums[left]
  }
  return res
}

复杂度

• 时间复杂度：$O(n)$，每个元素最多进入和离开窗口一次。
• 空间复杂度：$O(1)$，不计返回数组，只维护窗口和。

滑动窗口模板小结

这题和普通「长度为 k 的定长窗口」的区别在于：答案不是记录在窗口右端，而是记录在窗口中心。

for 右端 in 遍历:
    加入右端元素到窗口状态

    if 窗口未满:
        continue

    根据窗口左端计算中心位置
    更新中心位置的答案

    移除左端元素，左端右移