解
第一步，万年不变的查错。如果给的array是null或空，那么直接return。
public double maxAverage(int[] nums, int k) {
if (nums == null || nums.length == 0) {
return 0;
}
...
}
思路首先就是因为要找subarray的最大平均值，肯定需要知道每一个subarray的和，所以肯定就得用prefix sum。先把prefix sum做出来。Prefix Sum就是把从0到i的和全部存在一个数组里，这样只要用sums[j] - sums[i]就可以知道从i到j的subarray的和。
int n = nums.length;
long[] sums = new long[n + 1];
sums[0] = 0L;
for (int i = 0; i < n; i++) {
sums[i + 1] = sums[i] + nums[i];
}
然后最简单的做法就是Two Pointer遍历打擂台。找出所有大于k的字数组的平均值，然后return。
double maxAvg = Double.NEGATIVE_INFINITY;
for (int i = 0; i < n - k + 1; i++) {
for (int j = i + k; j < n + 1; j++) {
long sum = sums[j] - sums[i];
double avg = ((double) sum) / (j - i);
maxAvg = Math.max(maxAvg, avg);
}
}
return maxAvg;
这个做法可以过93%的测试。最后一个测试过不了是因为值很多，但是range很小，LintCode肯定是希望用二分法解的，所以时间卡的很小。但是这种方法肯定能解出来。
完整的code
public class Solution {
/*
* @param nums: an array with positive and negative numbers
* @param k: an integer
* @return: the maximum average
*/
public double maxAverage(int[] nums, int k) {
if (nums == null || nums.length == 0) {
return 0;
}
int n = nums.length;
long[] sums = new long[n + 1];
sums[0] = 0L;
for (int i = 0; i < n; i++) {
sums[i + 1] = sums[i] + nums[i];
}
double maxAvg = Double.NEGATIVE_INFINITY;
for (int i = 0; i < n - k + 1; i++) {
for (int j = i + k; j < n + 1; j++) {
long sum = sums[j] - sums[i];
double avg = ((double) sum) / (j - i);
maxAvg = Math.max(maxAvg, avg);
}
}
return maxAvg;
}
}
解2
二分法的解法，也得用prefix sum，但是用法不一样。先找出最大值最小值，作为range的start 跟end。
double start = (double) nums[0];
double end = (double) nums[0];
for (int i = 0; i < nums.length; i++) {
start = Math.min(start, nums[i]);
end = Math.max(end, nums[i]);
}
然后开始二分，找出中间数，看有没有一个平均值大于中间数的字数组存在，如果有，就把start放在中间，如果没有，就把end放在中间，然后继续二分。这里while的条件是end-start >= 1e-6，因为double是有小数点的，不能直接对比，所以要对比误差。
while (end - start >= 1e-6) {
double mid = start + (end - start) / 2;
if (checkValid(nums, k, mid)) {
start = mid;
} else {
end = mid;
}
}
return end;
怎样查存不存在这样的字数组呢？用prefix sum。但是不是来存和，而是和减去中间数。这样sums[j] - sums[i]就是从i到j的平均值减去中间数的结果。举个例子，[1, 2, 3]的sums是[0, 1, 3, 6]，如果中间数是1，那么每次计算下一个和的时候，减去中间数，sums就变成了[0, 0, 1, 3]。第一个不需要减，因为它代表size为0的字数组，只是用来帮助计算从第一个开始字数组的和。这样，我们就发现，如果i是0，j是1，那么 sums[j] - sums[i]的结果就是0，代表着如果这个只有1的字数组，平均值不大于我们的中间数1。而如果j是2，那么sums[j] - sums[i]的结果就是1，大于0，所以这个包含1，2的字数组，平均值就大于1。同理，如果中间数是2，我们就会发现sums变成了[0, -1, -1, 0]，所以任何两个数相减大于0，也就代表着最大的平均值不超过2。
public boolean checkValid(int[] nums, int k, double mid) {
double minPrev = 0;
double[] sums = new double[nums.length + 1];
sums[0] = 0.0;
for (int i = 0; i < nums.length; i++) {
sums[i + 1] = sums[i] + nums[i] - mid;
if (i + 1 >= k && sums[i + 1] - minPrev > 0) {
return true;
}
if (i + 1 >= k) {
minPrev = Math.min(minPrev, sums[i + 2 - k]);
}
}
return false;
}
具体实现的方法就是，在算sum的时候，用前一个sum加当前数字减去中间数。如果当前个数超过k个了，就找一下k个之前最小的数，这样当前sum减去之间最小的数才会是最大的结果。如果这个最大的结果超过0，代表着最大平均值超过了当前的中间数，那么返回，然后让二分法继续找下一个平均数。如果没有任何一个组合超过这个数，那么说明我们的中间数大于最大平均值，在往小的方向二分。
完整的code
public class Solution {
/*
* @param nums: an array with positive and negative numbers
* @param k: an integer
* @return: the maximum average
*/
public double maxAverage(int[] nums, int k) {
if (nums == null || nums.length == 0) {
return 0;
}
double start = (double) nums[0];
double end = (double) nums[0];
for (int i = 0; i < nums.length; i++) {
start = Math.min(start, nums[i]);
end = Math.max(end, nums[i]);
}
while (end - start >= 1e-6) {
double mid = start + (end - start) / 2;
if (checkValid(nums, k, mid)) {
start = mid;
} else {
end = mid;
}
}
return end;
}
public boolean checkValid(int[] nums, int k, double mid) {
double minPrev = 0;
double[] sums = new double[nums.length + 1];
sums[0] = 0.0;
for (int i = 0; i < nums.length; i++) {
sums[i + 1] = sums[i] + nums[i] - mid;
if (i + 1 >= k && sums[i + 1] - minPrev > 0) {
return true;
}
if (i + 1 >= k) {
minPrev = Math.min(minPrev, sums[i + 2 - k]);
}
}
return false;
}
}
分析
第一个解法，用prefix sum，空间是O(n)，时间因为two pointer遍历，是O((n-k)2)，也可以是O(n2)。
第二个解法，用二分法加prefix sum，空间还是O(n)，时间的话，二分需要O(log(max-min))，然后查找valid需要O(n)，所以总共就是O(nlog(max-min))。
总的来说，第一个解法更简便，也是面试时跟容易想到的一个解法。第二个实现更复杂一点，prefix sum减去中间数这种trick你硬要说面试中刚想到的也不大可信。而且log(max-min)纯粹取决于数值的大小。如果只有两个数，一个Integer.MIN_VALUE，一个Integer.MAX_VALUE，然后k是2，那么肯定第一种解法要比第二种解法快得多。第二种解法适合数很多，range很小，即n很大，max-min很小的案例。
网友评论