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

题目链接

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

题目描述

给定一个下标从 0 开始的整数数组 nums 和整数 k，构建并返回一个长度为 n 的数组 avgs，其中 avgs[i] 表示以下标 i 为中心、半径为 k 的子数组的平均值。具体规则如下：

无效位置：若 i 左侧不足 k 个元素（i - k < 0）或右侧不足 k 个元素（i + k >= n），则 avgs[i] = -1；
有效位置：若 i 前后均有至少 k 个元素（即子数组下标范围为 [i-k, i+k]，共 2k+1 个元素），则 avgs[i] 为该子数组元素的平均值（使用截断式整数除法，直接舍去小数部分）。

解法分析

代码实现

from typing import List  class Solution:  def getAverages(self, nums: List[int], k: int) -> List[int]:  s = 0  # 滑动窗口内元素的和  ans = [-1] * len(nums)  # 初始化结果数组，默认所有位置无效  for i in range(len(nums)):  s += nums[i]  # 将当前元素加入窗口和  if i < k * 2:  continue  # 窗口未形成完整长度时跳过计算  ans[i - k] = s // (2 * k + 1)  # 计算中心位置的平均值  s -= nums[i - 2 * k]  # 滑动窗口，移除左边界元素  return ans

代码详细分析

1. 初始化操作

s（窗口和）：用于存储当前滑动窗口内所有元素的和，初始化为 0。随着遍历进行，逐个累加数组元素，并在窗口滑动时减去离开窗口的元素，保持动态更新。
ans（结果数组）：初始化为全 -1，表示所有位置默认无效。后续有效位置会被覆盖为对应的平均值，无需额外处理无效位置的边界条件。

2. 遍历数组与窗口扩展

右指针 i：从 0 开始遍历数组的每个元素，每次将 nums[i] 加入窗口和 s，相当于将窗口的右边界扩展到当前元素 i。
窗口形成条件：当 i < 2k 时，窗口内元素个数为 i+1，而有效窗口需要 2k+1 个元素（例如 k=1 时需要3个元素，i=1 时只有2个），此时跳过计算，继续扩展窗口。

3. 有效窗口处理

窗口完整时：当 i >= 2k 时，窗口包含从 i-2k 到 i 的 2k+1 个元素（例如 k=3，i=6 时，窗口范围是 [0,6]，共7个元素），此时窗口以 i-k 为中心（左边界 i-2k 右移 k 步到达中心）。
平均值计算：使用截断式整数除法 s // (2k+1)，直接舍去小数部分，符合题目要求。

4. 窗口滑动更新

移除左边界元素：在计算完当前中心位置的平均值后，下一个窗口的左边界需要右移一位，即移除 nums[i-2k]（当前窗口的最左元素），确保下一次遍历的窗口大小仍为 2k+1。例如，当 i=6 处理完后，下一个窗口左边界从 0 变为 1，窗口范围变为 [1,7]。

案例分析

以 LeetCode 示例输入为例：
输入：nums = [7,4,3,9,1,8,5,2,6], k = 3
输出：[-1,-1,-1,5,4,4,-1,-1,-1]

分步计算过程

窗口大小：2k+1 = 7，有效中心位置需满足 i-3 >= 0 且 i+3 < 9，即 i ∈ [3, 5]（对应结果数组下标3、4、5）。
遍历过程：
- 当 i=6（下标6，元素5）：
  - 窗口和 s = 7+4+3+9+1+8+5 = 37；
  - i >= 2k=6，中心位置为 6-3=3，ans[3] = 37 // 7 = 5；
  - 移除左边界元素 nums[0]=7，s = 37-7=30。
- 当 i=7（下标7，元素2）：
  - 加入当前元素2，s = 30+2=32；
  - 中心位置为 7-3=4，ans[4] = 32 // 7 = 4；
  - 移除左边界元素 nums[1]=4，s = 32-4=28。
- 当 i=8（下标8，元素6）：
  - 加入当前元素6，s = 28+6=34；
  - 中心位置为 8-3=5，ans[5] = 34 // 7 = 4；
  - 移除左边界元素 nums[2]=3，但遍历结束，无需继续处理。
结果数组：
- 无效位置（如 i=0,1,2,6,7,8 因边界不足）保持初始值 -1，有效位置 3、4、5 分别赋值为 5、4、4，最终结果与示例一致。