動機
大概抓到sliding window的模式了
Problem
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 = 4Output: 12.75000Explanation: Maximum average is (12 - 5 - 6 + 50) / 4 = 51 / 4 = 12.75
Example 2:
Input: nums = [5], k = 1Output: 5.00000
Constraints:
n == nums.length
1 <= k <= n <= 105
-104 <= nums[i] <= 104
Sol
a = 0
win_cnt = sum(s[a:b-1])
for b in range(b-1,len(s)):
win_cnt += s[b]
f()
win_cnt -= s[a]
a += 1
class Solution:
def findMaxAverage(self, nums: List[int], k: int) -> float:
a, cnt = 0,0
ret = sum(nums[:k])/k
cnt = sum(nums[:k-1])*1.0
for b in range(k-1,len(nums)):
cnt += nums[b]
ret = max(ret, cnt/k)
cnt -= nums[a]
a+=1
return ret