2090. K 半径子数组的平均值

🎯 问题描述（来源于LeetCode）

描述：给你一个下标从 0 开始的数组 nums，对于每个下标 i，计算以 i 为中心且半径为 k 的子数组的平均值（向下取整）。如果不存在这样的子数组，则答案为 -1。

说明：

半径为 k 的子数组：指长度为 $2k+1$ 的连续子序列，中心点为 i。
如果下标 i 的左右两边无法容纳 k 个元素（即数组边界处），则无法形成子数组，结果为 -1。
示例 1：

输入：nums = [7,4,3,9,1,8,5,2,6], k = 3
输出：[-1,-1,-1,5,4,4,-1,-1,-1]
解释：
只有下标 3, 4, 5 能作为中心点形成长度为 7 的子数组。
avgs[3] = (7+4+3+9+1+8+5) // 7 = 37 // 7 = 5
````

- **示例 2**：

输入：nums = [100000], k = 0
输出：[100000]
解释：
当 k=0 时，半径为 0，子数组长度为 1，直接返回原值。


## 💻 解题思路

### 思路1：定长滑动窗口

#### 思路1：代码实现

class Solution:
def getAverages(self, nums: List[int], k: int) -> List[int]:
avgs = [-1] * len(nums) # 初始化结果数组，无法计算的位置默认为 -1
count = 0 # 维护当前滑动窗口内的元素总和

    for i, num in enumerate(nums):
        # 1. 扩展窗口：将当前元素加入总和
        count += num
        
        # 计算形成完整窗口所需的最小下标
        # 窗口长度为 2*k+1，所以当 i >= 2*k 时，窗口才第一次形成
        left = 2 * k
        
        # 2. 窗口未形成：如果 i < 2k，说明元素不足 (2k+1) 个，跳过计算
        if i < left:
            continue
            
        # 3. 窗口已形成：计算中心点的平均值
        # 当前窗口 [i-2k, i] 的中心点是 i-k
        avgs[i - k] = count // (2 * k + 1)
        
        # 4. 收缩窗口：移除最左边的元素（即下标为 i-2k 的元素）
        # 为下一次循环做准备，保持窗口大小为 2k+1
        count -= nums[i - left]
        
    return avgs


#### 思路1：📊 性能分析

- **运行时间**：O(N)
- **内存消耗**：O(1)
##### 复杂度验证

- **时间复杂度**：O(N)
    - 只需要遍历数组 `nums` 一次。每个元素被加入窗口一次，移出窗口一次，计算操作是常数时间。
- **空间复杂度**：O(1)
    - 除了存储结果的 `avgs` 数组外，仅使用了 `count` 和循环变量等常数个额外变量。

#### 思考

1. **索引映射**：这是本题最容易出错的地方。
    - 当前遍历的下标是 `i`（窗口右边界）。
    - 窗口的长度是 `2*k+1`。
    - 窗口的中心点（即需要填入答案的位置）是 `i - k`。
2. **边界处理**：
    - 代码巧妙地利用了 `avgs` 初始化为 `-1` 的特性。只有当窗口形成（`i >= 2*k`）时才会去修改 `avgs`，否则保持 `-1`，完美解决了边界无法计算的问题。
3. **整数除法**：
    - 题目要求“向下取整”，Python 中的 `//` 运算符正好满足要求。注意题目通常要求的是数学上的向下取整（Floor Division），对于非负数数组，直接使用整除即可。
4. **窗口维护**：
    - `left = 2 * k` 代表的是窗口长度减 1。`i - left` 即 `i - 2*k`，这是当前窗口最左边元素的下标，滑动时需要将其移除。