半径为 k 的子数组平均值

难度: Medium

给你一个下标从 0 开始的数组 nums ，数组中有 n 个整数，另给你一个整数 k 。

半径为 k 的子数组平均值 是指：nums 中一个以下标 i 为中心且半径为 k 的子数组中所有元素的平均值，即下标在 i - k 和 i + k 范围（含 i - k 和 i + k）内所有元素的平均值。如果在下标 i 前或后不足 k 个元素，那么 半径为 k 的子数组平均值 是 -1 。

构建并返回一个长度为 n 的数组 avgs ，其中 avgs[i] 是以下标 i 为中心的子数组的 半径为 k 的子数组平均值 。

x 个元素的 平均值 是 x 个元素相加之和除以 x ，此时使用截断式 整数除法 ，即需要去掉结果的小数部分。

例如，四个元素 2、3、1 和 5 的平均值是 (2 + 3 + 1 + 5) / 4 = 11 / 4 = 2.75，截断后得到 2 。

示例 1：

输入：nums = [7,4,3,9,1,8,5,2,6], k = 3
输出：[-1,-1,-1,5,4,4,-1,-1,-1]
解释：
- avg[0]、avg[1] 和 avg[2] 是 -1 ，因为在这几个下标前的元素数量都不足 k 个。
- 中心为下标 3 且半径为 3 的子数组的元素总和是：7 + 4 + 3 + 9 + 1 + 8 + 5 = 37 。
  使用截断式 整数除法，avg[3] = 37 / 7 = 5 。
- 中心为下标 4 的子数组，avg[4] = (4 + 3 + 9 + 1 + 8 + 5 + 2) / 7 = 4 。
- 中心为下标 5 的子数组，avg[5] = (3 + 9 + 1 + 8 + 5 + 2 + 6) / 7 = 4 。
- avg[6]、avg[7] 和 avg[8] 是 -1 ，因为在这几个下标后的元素数量都不足 k 个。

示例 2：

输入：nums = [100000], k = 0
输出：[100000]
解释：
- 中心为下标 0 且半径 0 的子数组的元素总和是：100000 。
  avg[0] = 100000 / 1 = 100000 。

示例 3：

输入：nums = [8], k = 100000
输出：[-1]
解释：
- avg[0] 是 -1 ，因为在下标 0 前后的元素数量均不足 k 。

提示：

n == nums.length
1 <= n <= 10⁵
0 <= nums[i], k <= 10⁵

Submission

运行时间: 109 ms

内存: 29.8 MB

class Solution:
    def getAverages(self, nums: List[int], k: int) -> List[int]:
        if k == 0:
            return nums
        l = 2*k + 1
        n = len(nums)
        num = sum(nums[:l])
        f = [-1] * n

        if n > l:
            f[k] = num // l
        elif n == l:
            f[k] = num // l
            return f
        else:
            return f

        for i in range(k+1, n-k):
            num -= nums[i-k-1]
            num += nums[i+k]
            f[i] = num // l
        return f

Explain

本题解采用了滑动窗口的算法策略。首先，检查特殊情况，如果 k 为 0，直接返回原数组 nums，因为不需要任何窗口操作。接下来，计算窗口长度 l 为 2*k + 1，这是因为窗口需要覆盖从 i-k 到 i+k 的元素。初始化一个长度为 n 的数组 f，全部填充为 -1，用来存储最终的结果。通过在 nums 的开始计算初始窗口的总和 num。如果 n 大于等于 l，说明存在至少一个合法的窗口，将首个窗口的平均值存入 f[k]。然后，利用滑动窗口技术，依次更新窗口中的元素总和，计算并更新每个合法窗口的平均值。这个过程一直进行，直到无法再形成一个完整的窗口，即窗口的右边界超出了数组的长度。最后，返回填充好的数组 f。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def getAverages(self, nums: List[int], k: int) -> List[int]:
        if k == 0:
            return nums  # k为0时，直接返回原数组
        l = 2*k + 1  # 计算窗口的宽度
        n = len(nums)
        if n < l:
            return [-1] * n  # 如果数组长度小于窗口宽度，直接返回全为-1的数组
        num = sum(nums[:l])  # 计算初始窗口的元素总和
        f = [-1] * n  # 初始化结果数组为-1

        if n >= l:
            f[k] = num // l  # 计算第一个窗口的平均值并存储

        for i in range(k+1, n-k):
            num -= nums[i-k-1]  # 移除窗口最左边的元素
            num += nums[i+k]  # 添加窗口最右边的新元素
            f[i] = num // l  # 计算新窗口的平均值并存储
        return f  # 返回计算得到的结果数组

Explore

在这个题解中，窗口的大小是固定的，长度为`2*k + 1`，即`l`。为了计算第一个窗口（覆盖数组中从位置0到位置`2*k`的元素）的平均值，必须首先计算这个窗口中所有元素的总和。这就是为什么使用`sum(nums[:l])`来计算初始窗口的总和，因为这正好覆盖了初始窗口需要的元素范围。使用其他范围的元素将无法正确反映第一个窗口的情况。

在滑动窗口技术中，更新操作`num -= nums[i-k-1]; num += nums[i+k]`用于移除窗口左端的一个元素并添加一个新的元素至窗口右端。这种操作保证了窗口内的元素数量总是保持不变，即`2*k + 1`个元素。当窗口从一个位置滑向下一个位置时，只需移除当前窗口最左端的元素，并加上一个新的最右端的元素，这样可以有效地更新窗口的总和而不需要重新计算整个窗口内的元素总和，从而提高了效率。

当数组长度`n`小于窗口长度`l`时，意味着无法形成一个完整的窗口（因为窗口需要`2*k + 1`个元素）。因此，在任何情况下，只要`n < l`，不论是`n=0`还是`k>n`，返回全为-1的数组都是有效的处理方式，因为这些情况下都不可能形成一个有效的滑动窗口来计算平均值。

在题解中使用的是整数除法`num // l`主要是因为题目可能期望返回结果为整数。此操作确实可能导致精度问题，因为它会丢弃小数部分，只保留结果的整数部分。如果题目需要更精确的结果，可以考虑使用浮点数除法并四舍五入到最接近的整数。不过，具体取决于题目的要求和预期的输出格式。