[Leetcode] 643. Maximum Average Subarray I

643. Maximum Average Subarray I
Given an array consisting of n integers, find the contiguous subarray of given length k that has the maximum average value. And you need to output the maximum average value.
Example 1:
Input: [1,12,-5,-6,50,3], k = 4
Output: 12.75
Explanation: Maximum average is (12-5-6+50)/4 = 51/4 = 12.75
Note:
  1. 1 <= k <= n <= 30,000.
  2. Elements of the given array will be in the range [-10,000, 10,000].
easy难度的,应该没啥弯弯绕。但是有一点,要问清楚每个数字大小,数组有多少数字。确保1. 每个数字不overflow了Max int
2. 他们的和不overflow了Max int
如果数字太大, 就要用string 求和的方法了。鉴于这道题是easy,题目给的note里就有限制了,所以这道题我们不用担心。

尝试了一格一格挪,每次取k个数加起来的最原始办法, 复杂度应该是nk果然超时了TLE。。。就在用这个原始方法的时候,也出了问题了,我在for循环里的limit是nums.length-k,实际上应该是nums.length-k+1. 然鹅,事实是这个样子滴,在我们单独讲循环某个数组的时候,limit应该是小于这个数组的长度,因为等于长度就读不出来数了,当从0开始算index的时候。

但是向这类的移动平均值呢,这个limit的物理意义是,我们要移动多少下。不举具体数字栗子,就干想我们有一个数组,长度是n,要取window长度为k的平均值。我们把长度为n的数组和长度为k的数组上下摞起来,多出来的就是n-k。但是!我们并不能设置limit为n-k,因为,这样我们就少移动了一次,最后一个k的window我们没有读到!


好吧,第二招,稍微不那么笨的,就是把当前算好的减去第一个数,加上向后挪一个的数。喜大普奔啊,代码两次就过了,而且击败了全球83%。好像是目前的最好战绩了呢!大神们请绕路。。。再绕回来然后,欢迎大神指点啊,本渣感激不尽!

通过这个easy的小题目呢,我们明白了一个道理:
1. for循环物理意义是次数,在这里就是移动的次数;
2. 不用管for 的int i 起始k是啥,(i<,用小于号的时候)循环的次数等于limit-k;
3. 这个window每个里面有k个数值,首尾相隔k-1个数。所以每次计算减掉上次求和数组前面的一个数,在加上当前的数,中间相隔k个数;
4. 那么问题来了,既然for循环是看移动的次数,那么,我们说好的移动n-k+1次移动,怎么limit是n,起点是k,那不就是n-k了?lol。。。聪明的你想到答案了吗?
答案见最下边。




AC Solution:

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        // The number has a limit, which all the sum max will not exceed max int
        double lastSum = 0;
        for(int i=0; i<k; i++){
            lastSum += nums[i];
        }
        double maxAvg = lastSum/k;
        for(int i=k; i<nums.length; i++){
            double curSum = 0;
            curSum = lastSum-nums[i-k]+nums[i];
            maxAvg = Math.max(maxAvg, curSum/k);
            lastSum = curSum;
        }
        return maxAvg;
    }
}

答案:我们计算初始maxAvg的时候算过一次啊!捂脸哭,我卡着卡了好久,百思不得其解。。。蠢哭


Comments

Popular posts from this blog

LeetCode] 644.Maximum Average Subarray II

[Leetcode]375. Guess Number Higher or Lower II