643.子数组最大平均数I

643-子数组最大平均数I

题目

给你一个由 n 个元素组成的整数数组 nums 和一个整数 k 。

请你找出平均数最大且 长度为 k 的连续子数组，并输出该最大平均数。

任何误差小于 10-5 的答案都将被视为正确答案。

示例 1：

1
2
3
输入：nums = [1,12,-5,-6,50,3], k = 4
输出：12.75
解释：最大平均数 (12-5-6+50)/4 = 51/4 = 12.75

示例 2：

1
2
输入：nums = [5], k = 1
输出：5.00000

提示：

  • n == nums.length
  • 1 <= k <= n <= 105
  • -104 <= nums[i] <= 10

解题思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public double findMaxAverage(int[] nums, int k) {
        double res=-Double.MAX_VALUE;
        double sum=0;
        if(nums.length==1)  return nums[0];
        for(int i=0;i<=nums.length-k;i++){
            for(int j=i;j<i+k;j++){
                sum+=nums[j];
            }
            res=Math.max(res,sum);
            sum=0;
        }
        return res/k;
    }
}

我一开始的代码是这样写的：

通过双重循环遍历所有长度为 k 的连续子数组，计算每个子数组的和 sum，并记录最大的和 res，最后返回 res / k 作为最大平均值。外层循环控制子数组的起始位置，内层循环累加子数组元素，每次比较并更新最大值后重置 sum 为 0。

很显然，最终的结果超时了，因此，我们要采用滑动窗口来解决。

先来介绍滑动窗口：

滑动窗口是一种高效的算法技巧，用于解决数组或字符串中的连续子序列问题。它通过动态维护一个窗口（由左右指针定义的区间），在遍历数据时，根据条件灵活调整窗口的大小和位置，从而避免重复计算，将时间复杂度优化至O(n)。滑动窗口分为两种类型：固定长度窗口（如计算长度为k的子数组最大平均值，通过加减边界元素快速更新窗口和）和可变长度窗口（如寻找最长无重复子串，通过移动指针动态扩展或收缩窗口）。其核心思想是利用窗口的滑动复用已有计算结果，取代暴力解法的多次遍历，典型应用包括子数组和、最短/最长满足条件的子串等问题，兼具简洁性和高效性。

滑动窗口的核心思想

  1. 窗口定义
    窗口是数组/字符串中由左右指针（left, right）划定的一段连续区间。窗口会根据条件动态扩展或收缩。
  2. 窗口移动规则
    • 右指针（right）：向右扩展窗口，代表探索新的元素。
    • 左指针（left）：向右收缩窗口，代表排除不符合条件的元素。
  3. 核心优势
    通过复用窗口内的计算结果，避免重复遍历，显著提升效率。

滑动窗口的两种类型

1. 固定长度窗口

  • 窗口大小固定（如题目中长度 k 的子数组）。

  • 实现步骤：

    1. 初始化窗口：计算第一个窗口的和/值。
    2. 滑动窗口：每次移动时，加上右边新元素，减去左边旧元素。
    1
    2
    3
    4
    5
    6
    7
    8
    // 示例：计算长度为k的子数组最大平均值
    double sum = 0;
    for (int i = 0; i < k; i++) sum += nums[i]; // 初始窗口
    double maxAvg = sum / k;
    for (int i = k; i < nums.length; i++) {
        sum += nums[i] - nums[i - k]; // 滑动窗口
        maxAvg = Math.max(maxAvg, sum / k);
    }

2. 可变长度窗口

  • 窗口大小根据条件动态变化（如”最长无重复子串”问题）。

  • 实现步骤：

    1. 初始化左右指针 left = right = 0。
    2. 移动右指针扩展窗口，直到不满足条件。
    3. 移动左指针收缩窗口，直到重新满足条件。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    // 示例：最长无重复子串
    int left = 0, maxLen = 0;
    Set<Character> window = new HashSet<>();
    for (int right = 0; right < s.length(); right++) {
        while (window.contains(s.charAt(right))) { // 不满足条件时收缩
            window.remove(s.charAt(left++));
        }
        window.add(s.charAt(right));
        maxLen = Math.max(maxLen, right - left + 1);
    }

滑动窗口的应用场景

  1. 固定窗口问题
    • 子数组最大/最小平均值（如本题）
    • 长度为k的最大和子数组
  2. 可变窗口问题
    • 最长无重复字符子串（LeetCode 3）
    • 最小覆盖子串（LeetCode 76）
    • 满足条件的最短子数组（如和≥target）

为什么滑动窗口高效？

以本题为例：

  • 暴力解法：对每个子数组重新计算和，时间复杂度 O(n*k)。
  • 滑动窗口：通过 sum += nums[right] - nums[left] 复用前一个窗口的结果，只需 O(n)。

滑动窗口模板（可变长度）

1
2
3
4
5
6
int left = 0; // 窗口左边界
for (int right = 0; right < n; right++) { // 窗口右边界
    // 1. 将nums[right]加入窗口
    // 2. while (窗口不满足条件) { 移动left缩小窗口 }
    // 3. 更新结果（如最大长度/最短长度等）
}

掌握滑动窗口的关键在于明确窗口的移动条件和如何高效更新计算结果。

最终代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public double findMaxAverage(int[] nums, int k) {
        int sum=0;
        // 计算初始窗口的和
        for(int i=0;i<k;i++){
            sum+=nums[i];
        }
        int maxSum=sum;
        // 滑动窗口，更新最大值
        for (int i=k;i<nums.length;i++){
            sum=sum-nums[i-k]+nums[i];
            maxSum=Math.max(maxSum,sum);
        }
        return (double)maxSum/k;
    }
}