跳至主要內容

0643. 子数组最大平均数 I

ITCharge大约 2 分钟

0643. 子数组最大平均数 Iopen in new window

  • 标签:数组、滑动窗口
  • 难度:简单

题目链接

题目大意

描述:给定一个由 nn 个元素组成的整数数组 numsnums 和一个整数 kk

要求:找出平均数最大且长度为 kk 的连续子数组,并输出该最大平均数。

说明

  • 任何误差小于 10510^{-5} 的答案都将被视为正确答案。
  • n==nums.lengthn == nums.length
  • 1kn1051 \le k \le n \le 10^5
  • 104nums[i]104-10^4 \le nums[i] \le 10^4

示例

  • 示例 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

解题思路

思路 1:滑动窗口(固定长度)

这道题目是典型的固定窗口大小的滑动窗口题目。窗口大小为 kk。具体做法如下:

  1. ansans 用来维护子数组最大平均数,初始值为负无穷,即 float('-inf')windowtotalwindow\underline{}total 用来维护窗口中元素的和。
  2. leftleftrightright 都指向序列的第一个元素,即:left = 0right = 0
  3. 向右移动 rightright,先将 kk 个元素填入窗口中。
  4. 当窗口元素个数为 kk 时,即:rightleft+1>=kright - left + 1 >= k 时,计算窗口内的元素和平均值,并维护子数组最大平均数。
  5. 然后向右移动 leftleft,从而缩小窗口长度,即 left += 1,使得窗口大小始终保持为 kk
  6. 重复 454 \sim 5 步,直到 rightright 到达数组末尾。
  7. 最后输出答案 ansans

思路 1:代码

class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        left = 0
        right = 0
        window_total = 0
        ans = float('-inf')
        while right < len(nums):
            window_total += nums[right]

            if right - left + 1 >= k:
                ans = max(window_total / k, ans)
                window_total -= nums[left]
                left += 1

            # 向右侧增大窗口
            right += 1

        return ans

思路 1:复杂度分析

  • 时间复杂度O(n)O(n)。其中 nn 为数组 numsnums 的元素个数。
  • 空间复杂度O(1)O(1)