【Leetcode】643. Maximum Average Subarray I

Description

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

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].

Solution

public double findMaxAverage(int[] nums, int k) {
        int max = Integer.MIN_VALUE;
        int len = nums.length;
        if (k > len || nums == null) {
            return 0;
        }
        if (k == len) {
            int result = 0;
            for (int n : nums) {
                result += n;
            }
            return result;
        }
        for (int i = 0; i < len - k + 1; i++ ) {
            int tempSum = 0;
            for (int j = i; j < i + k; j++) {
                tempSum += nums[j];
            }
            max = Math.max(max, tempSum);
        }
        return (double)max / k;
    }

Result

Analyse

考虑了几种边界情况，但是略显复杂吧，时间复杂度O(n * k)，空间复杂度O(1)。标准答案里写的会更短，但是意思一样：

public double findMaxAverage(int[] nums, int k) {
        double result = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length - k + 1; i++) {
            double temp = 0;
            for (int j = 0; j < k; j++) {
                temp += nums[j];
            }
            result = Math.max(result, temp / k);
        }
        return result;
    }

Optimization

First

public double findMaxAverage(int[] nums, int k) {
        int len = nums.length;
        int[] sums = new int[nums.length];
        int temp = 0;
        for (int i = 0; i < len; i++) {
            temp += nums[i];
            sums[i] = temp;
        }
        double result = sums[k - 1];
        for (int j = k; j < len; j++) {
            result = Math.max(result, sums[j] - sums[j - k]);
        }
        return result / k;
    }

Analyse

这个方法很精妙，就是新建了一个sums数组，这样初始值好定，接下来的比较也很容易，易于思考，但是这样的话，虽然时间复杂度变成了O(n)，但是空间复杂度也成了O(n)，因为建立了一个n大小的数组。

Second

public double findMaxAverage(int[] nums, int k) {
        double res = Integer.MIN_VALUE;
        int len = nums.length;
        double temp = 0;
        for (int i = 0; i < k; i++) {
            temp += nums[i];
        }
        res = Math.max(res, temp / k);
        for (int j = k; j < nums.length; j++) {
            temp += nums[j] - nums[j - k];
            res = Math.max(res, temp / k);
        }
        return res;
    }

Analyse

一样的思路，但是这个空间复杂度降低到了O(1)，这个方法应该是最优的。但是这里要注意一个问题，在开始写这个思路的时候，我是这么写的：

public double findMaxAverage(int[] nums, int k) {
        int len = nums.length;
        double temp = 0;
        for (int i = 0; i < k; i++) {
            temp += nums[i];
        }
        for (int j = k; j < len; j++) {
            temp = Math.max(temp, temp + nums[j] - nums[j - k]);
        }
        return temp / k;
    }

这样的方法是存在问题的，比如说数组是int[] nums = {0,4,0,3,2};k = 1;这种情况下，你走到i = 2的时候，最大的还是4，但是当i = 3，nums[i] - nums[i - 1] = 3,这样就得到了7，这个是不对的，你得重新申请一个数来保存最终结果进行更新。