LeetCode 子数组最大平均数 I

2021-03-06 本文已影响0人吴敬悦

给定 n 个整数，找出平均数最大且长度为 k 的连续子数组，并输出该最大平均数。

示例：

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

提示：

1 <= k <= n <= 30,000。
所给数据范围 [-10,000，10,000]。

我的算法实现：

      /**
       * @param {number[]} nums
       * @param {number} k
       * @return {number}
       */
      var findMaxAverage = function (nums, k) {
        let maxAvg = Number.NEGATIVE_INFINITY;
        const len = nums.length;
        for (let i = 0; len - i >= k; i++) {
          const avg = nums.slice(i, k + i).reduce((a, b) => a + b) / k;
          if (maxAvg < avg) {
            maxAvg = avg;
          }
        }
        return maxAvg;
      };

最先开始我使用 kotlin 来实现的，但是我发现使用 kotlin 的方式，会出现超出时间限制，于是我就使用 javascript 来实现，发现这个还是能通过的，就是耗时较久，主要的原因就是这个算法是 O(n^2) 级别的算法，在数量增加的时候会明显比 O(n) 的慢很多。所以我就想到能不能先把前面的计算出来，然后每计算一个比较一个，结果我发现，如果加上去了，那么第二个连续的，由于没有第一个元素，但是由于经过第一轮拿到的和是前面所有的和，这时我就放弃了，我忘了传进来的数组里面有那些要减出去的值。

下次在考虑问题的时候，或者在优化什么的时候，可能尝试先看看自己手里有什么，这样就不会轻易忽视已知条件了。

下面是看到官网后，我使用 kotlin 写出来的：

class Solution {
    fun findMaxAverage(nums: IntArray, k: Int): Double {
        // 保存连续子元素的和
        var sum = 0
        // 数组的长度
        val len = nums.size
        // 先计算第一组连续数组的和
        for (i in 0 until k) {
            sum += nums[i]
        }
        // 默认让第一组的和为最大值
        var max = sum
        for (i in k until len) {
            // 从下一组开始，都要减去上一组的第一个元素
            sum = sum - nums[i - k] + nums[i]
            // 保存最新的最大值
            max = max.coerceAtLeast(sum)
        }
        return max/k.toDouble()
    }
}

这个的时间复杂度是 O(n) 级别的，所以在 kotlin 中也能正常运行下去。看我的思路，我为了保证最小值，使用了 Number.NEGATIVE_INFINITY ，因为没法保证我设置的任意数不是最大数，所以使用了这种方法，看到这个方法，可以知道，说不一定有一种像这道算法题一样，可以进行先操作，然后把选操作的保存为最大值。

来源：力扣（LeetCode）

LeetCode 子数组最大平均数 I

猜你喜欢

热点阅读