LeetCode643 子数组最大平均数 I

发表于

这是我参与11月更文挑战的第28天，活动详情查看：2021最后一次更文挑战。

题目描述：

643. 子数组最大平均数 I - 力扣（LeetCode） (leetcode-cn.com)

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

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

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

示例一

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

示例二

1
2
ini复制代码输入： nums = [5], k = 1
输出： 5.00000

提示：

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

思路分析

滑动窗口

根据题意，我们的长度为固定的K，既然长度固定，那么平均值最大即代表和最大，我们只需要一个长度为k的窗口，每次求出这个窗口内的k个数的和，同时记录，等下一次与这次比较，两者取其大

这有个小小的优化点就是，我们每向右边移动一步，其实不必再重新求和，这样如果k很大的话，会造成很多的浪费，每次滑动我们只需要将上次的和减去滑出去(头)再加上滑进来(尾)的即可得到本次的和。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Kotlin复制代码class Solution {
    fun findMaxAverage(nums: IntArray, k: Int): Double {
        var sum = 0
        for(i in 0 until k) {
            sum += nums[i]
        }
        var maxSum = sum
        for(i in k until nums.size) {
            sum = sum - nums[i-k] + nums[i]
            maxSum = Math.max(maxSum,sum)
        }
        return maxSum.toDouble() / k
    }
}

总结

滑动窗口类的题还是很容易理解的，知名见意，我们就当手上拿了一个长度为k的框框套在数组上即可。

参考

子数组最大平均数 I - 子数组最大平均数 I - 力扣（LeetCode） (leetcode-cn.com)

643. 子数组最大平均数 I - 子数组最大平均数 I - 力扣（LeetCode） (leetcode-cn.com)

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%