113 - 643 子数组最大平均数1

题目

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

示例 1:

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

注意:

1. 1 <= k <= n <= 30,000。

2. 所给数据范围 [-10,000，10,000]。

解答

平均数最大，也就是加和最大。关键要是连续的k个数。

两个for循环

var findMaxAverage = function(nums, k) {
  let sum = 0
  for (let i = 0; i < k; i++) {
    sum += nums[i]
  }
  let max = sum
  for (let i = k; i < nums.length; i++) {
    sum += nums[i] - nums[i - k]
    max = Math.max(max, sum)
  }
  return max / k
};

Runtime: 84 ms, faster than 81.92% of JavaScript online submissions for Maximum Average Subarray I.

Memory Usage: 42.7 MB, less than 100.00% of JavaScript online submissions for Maximum Average Subarray I.

class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        _max = _sum = sum(nums[0:k])
        for i in range(k, len(nums)):
            _sum += nums[i]-nums[i-k]
            _max = max(_max, _sum)
        return _max/k

Runtime: 988 ms, faster than 54.93% of Python3 online submissions for Maximum Average Subarray I.

Memory Usage: 17.6 MB, less than 12.50% of Python3 online submissions for Maximum Average Subarray I.

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
func findMaxAverage(nums []int, k int) float64 {
    var sum int
    for i := 0; i < k; i++ {
        sum += nums[i]
    }
    _max := sum
    for i := k; i < len(nums); i++ {
        sum += nums[i] - nums[i-k]
        _max = max(_max, sum)
    }
    return float64(_max) / float64(k)
}

Runtime: 128 ms, faster than 62.96% of Go online submissions for Maximum Average Subarray I.

Memory Usage: 7.7 MB, less than 100.00% of Go online submissions for Maximum Average Subarray I.

一个for循环

循环里面要加上两个if判断，感觉成本可能会更高

var findMaxAverage = function(nums, k) {
  let sum = 0
  let max = Number.MIN_SAFE_INTEGER
  for (let i = 0; i < nums.length; i++) {
    sum += nums[i]
    if (i >= k) {
      sum -= nums[i - k]
    }
    if (i >= k - 1) {
      max = Math.max(max, sum)
    }
  }
  return max / k
};

Runtime: 104 ms, faster than 33.82% of JavaScript online submissions for Maximum Average Subarray I.

Memory Usage: 42.7 MB, less than 100.00% of JavaScript online submissions for Maximum Average Subarray I.

确实如此吼

还有用数组的方法，感觉更加费成本了。