leetcode
leetcode 551 ~ 600
子数组最大平均数 I

子数组最大平均数 I

难度:

标签:

题目描述

代码结果

运行时间: 72 ms, 内存: 25.1 MB


/*
 思路:
 1. 使用Java Stream API来实现同样的逻辑。
 2. 首先计算前 k 个元素的和,并初始化最大和为此值。
 3. 使用流操作在数组上滑动窗口,每次减去窗口的第一个元素,加上新的元素,并更新最大和。
*/
import java.util.stream.IntStream;
 
public class SolutionStream {
    public double findMaxAverage(int[] nums, int k) {
        // 计算前 k 个元素的和
        int currentSum = IntStream.range(0, k).map(i -> nums[i]).sum();
        int maxSum = currentSum;
        // 滑动窗口
        for (int i = k; i < nums.length; i++) {
            currentSum += nums[i] - nums[i - k];
            maxSum = Math.max(maxSum, currentSum);
        }
        // 返回最大平均数
        return (double) maxSum / k;
    }
}

解释

方法:

此题解采用了滑动窗口的方法来寻找具有最大平均值的长度为 k 的子数组。首先,如果数组的长度 n 等于 k,直接返回整个数组的平均值。否则,首先计算前 k 个元素的和作为初始的子数组和。然后,使用一个循环,通过从当前子数组和中减去最左边的元素并加上紧随其后的下一个元素来更新子数组的和,从而向右滑动窗口。每次更新后,如果发现更大的子数组和,则更新最终的最大和。最后,返回最大和除以 k 得到的结果。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
为什么在该算法中,当数组长度n等于k时,直接返回整个数组的平均值被认为是最优解?
当数组长度n等于k时,只存在一个可能的子数组,即整个数组本身。因此,这个子数组的平均值就是整个数组的平均值。在这种情况下,没有其他子数组可以考虑,所以直接计算并返回整个数组的平均值是最快且唯一的解决方案。
🦆
在滑动窗口中,tmp_ans是如何确保不会因为整数溢出而导致错误计算?
在Python中,整数类型是动态扩展的,这意味着它可以处理非常大的数值而不会像在固定大小的整数类型中那样溢出。因此,在使用Python进行滑动窗口操作时,tmp_ans更新时并不需要特别处理整数溢出问题。但在其他编程语言中,如Java或C++,开发者需要注意数据类型的最大和最小限制,可能需要采用更大的数据类型或进行额外的检查以防止溢出。
🦆
为什么只有在tmp_ans大于fin_ans时才更新fin_ans,而不是每次都更新,这样做有什么优点?
该策略的目的是找到最大的子数组平均值。通过仅在tmp_ans(当前滑动窗口的和)大于已知的最大和fin_ans时更新fin_ans,可以确保fin_ans始终包含可能的最大和,避免了不必要的赋值操作。这样做可以减少赋值操作的次数,提高算法的效率,尤其是在tmp_ans经常小于fin_ans的情况下。
🦆
这个算法在处理极端情况下(例如所有元素都是负数或都是正数)时的表现如何?
这个算法在处理所有元素都是负数或都是正数的情况下仍然有效。如果所有元素都是负数,算法能正确找到最大的(最不负)平均值;如果所有元素都是正数,算法则能找到最大的平均值。这是因为算法基本逻辑是通过比较不同子数组的和来确定最大平均值,无论数组的具体数值如何,这种比较机制都是有效的。

相关问题

子数组最大平均数 II

子数组最大平均数 II