子数组最大平均数 I

2025-04-25

描述

给你一个由 n 个元素组成的整数数组 nums 和一个整数 k 。请你找出平均数最大且长度为 k 的连续子数组，并输出该最大平均数。任何误差小于 10-5 的答案都将被视为正确答案。

解题思路

计算初始窗口和
- 首先计算数组中前 k 个元素的和，这是第一个长度为 k 的子数组的和。
滑动窗口遍历
- 然后使用滑动窗口的思想。从第 k 个元素开始向后遍历数组。
- 在每次遍历中，通过将当前窗口的和减去窗口最左边的元素（上一个窗口中最左边的元素），再加上当前遍历到的元素（作为新窗口最右边的元素），来更新窗口的和。
记录最大和
- 在每次更新窗口和后，比较当前窗口的和与之前记录的最大和。
- 如果当前窗口的和更大，则更新最大和。
计算最大平均数
- 最后，将最大和除以 k，得到长度为 k 的连续子数组中的最大平均数。

代码实现

    public double findMaxAverage(int[] nums, int k) {
        int len = nums.length;
        int sum = Integer.MIN_VALUE;
        int temp = 0;
        for (int i = 0; i < len; i++) {
            // 入：下标为 i 的元素进入窗口，更新统计量
            temp += nums[i];
            // 如果窗口长度不足，则继续
            if (i <= k - 1) {
                continue;
            }
            // 更新：更新结果值，最大值/最小值/平均值。。。
            sum = Math.max(sum, temp);
            // 出：窗口中 i-k+1 的元素离开，更新统计量
            temp -= nums[i - k + 1];
        }
        return (double) sum / k;
    }

class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        # 初始窗口大小为 k，计算数组中前 k 个值的和作为子数组最大和
        temp = sum(nums[:k])
        max_sum = temp
        # 遍历 k 后的元素
        for i in range(k, len(nums)):
            # 更新滑动窗口，右侧元素进窗口，左侧元素出窗口
            temp = temp - nums[i - k] + nums[i]
            # 更新最大值
            max_sum = max(max_sum, temp)
        return max_sum / k

nums[:k] 是 Python 中对数组（通常指列表）进行切片的一种操作。这里的切片操作从列表的开头（索引 0）开始，截取到索引 k 但不包含索引 k 的元素，返回一个新的列表。

Tips

`range` 函数在 Python 的三种常见用法：

range(stop)：
- 生成一个从 0 开始，到 stop 结束（但不包含 stop）的整数序列。例如 range(5)，会生成 0, 1, 2, 3, 4 这个序列，常被用于 for 循环中迭代固定次数，比如：
```
for i in range(5):
 print(i)
```
range(start, stop)：
- 生成一个从 start 开始，到 stop 结束（同样不包含 stop）的整数序列。例如 range(2, 7)，会生成 2, 3, 4, 5, 6 这个序列。示例代码：
```
for i in range(2, 7):
 print(i)
```
range(start, stop, step)：
- step 为步长，决定生成序列中数字的增长幅度。生成一个从 start 开始，到 stop 结束（不包含 stop），每次增加 step 的整数序列。例如 range(1, 10, 2)，会生成 1, 3, 5, 7, 9。示例如下：
```
for i in range(1, 10, 2):
 print(i)
```

`sum` 函数在 Python 中的几种常见用法：

sum(iterable)：
- 接受一个可迭代对象作为参数，例如列表、元组等，对其中所有元素进行求和操作。例如 sum([2, 4, 6])，会计算列表 [2, 4, 6] 中元素之和，返回 12。示例代码：
```
numbers = [2, 4, 6]
result = sum(numbers)
print(result) 
```
sum(iterable, start)：
- 第一个参数是可迭代对象，第二个参数 start 是可选的起始值（默认为 0）。它先将起始值与可迭代对象中的所有元素相加。例如 sum([1, 2, 3], 5)，会返回 1 + 2 + 3 + 5 = 11。示例如下：
```
nums = [1, 2, 3]
start = 5
total = sum(nums, start)
print(total) 
```

总结

通过滑动窗口方法，先初始化窗口和，接着在遍历中动态更新窗口和并比较得到最大和，最终计算最大平均数。 ^^

https://leetcode.cn/problems/maximum-average-subarray-i/description