643. 子数组最大平均数 I

🟢   🔖  数组 滑动窗口  🔗 力扣 LeetCode

题目

You are given an integer array nums consisting of n elements, and an integer k.

Find a contiguous subarray whose length is equal to k that has the maximum average value and return this value. Any answer with a calculation error less than 10^-5 will be accepted.

Example 1:

Input: nums = [1,12,-5,-6,50,3], k = 4

Output: 12.75000

Explanation: Maximum average is (12 - 5 - 6 + 50) / 4 = 51 / 4 = 12.75

Example 2:

Input: nums = [5], k = 1

Output: 5.00000

Constraints:

• n == nums.length
• 1 <= k <= n <= 10^5
• -10^4 <= nums[i] <= 10^4

题目大意

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

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

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

示例 1：

输入： nums = [1,12,-5,-6,50,3], k = 4

输出： 12.75

解释： 最大平均数 (12-5-6+50)/4 = 51/4 = 12.75

示例 2：

输入： nums = [5], k = 1

输出： 5.00000

提示：

• n == nums.length
• 1 <= k <= n <= 10^5
• -10^4 <= nums[i] <= 10^4

解题思路

1. 滑动窗口：

   • 使用滑动窗口来计算连续子数组的和，以便高效地找到最大平均值；
   • 初始化当前和 sum 和最大和 maxSum；

2. 更新窗口：

   • 在每次迭代中更新 sum；
   • 当索引 i 大于等于 k 时，减去窗口左侧的元素，以保持窗口大小为 k；

3. 更新最大和：

   • 一旦当前索引 i 达到 k - 1，就开始比较并更新最大和 maxSum；

4. 计算平均值：

   • 最后，根据最大和计算平均值并返回；

复杂度分析

• 时间复杂度：O(n)，遍历数组一次。
• 空间复杂度：O(1)，只使用常量空间来存储状态。

代码

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findMaxAverage = function (nums, k) {
	let sum = 0,
		maxSum = -Infinity;

	// 滑动窗口
	for (let i = 0; i < nums.length; i++) {
		// 更新当前和
		sum += nums[i];

		// 缩小窗口
		if (i >= k) {
			sum -= nums[i - k];
		}

		// 更新最大和
		if (i >= k - 1) {
			maxSum = Math.max(maxSum, sum);
		}
	}

	// 返回最大平均值
	return maxSum / k;
};

相关题目

题号	标题	题解	标签	难度
644	子数组最大平均数 II 🔒		数组 二分查找 前缀和
2090	半径为 k 的子数组平均值		数组 滑动窗口