Need help. O(n) sliding-window based solution passes most test cases but couldn't figure out what's wrong.


  • 0
    V
    public class Solution {
        public double findMaxAverage(int[] nums, int k) {
            if(nums == null || nums.length == 0 || k < 1 || nums.length < k) return 0.0;
            int len = nums.length;
            if(len == 1) return (double)nums[0];
            double sum = 0;
            for(int i=0; i<k; i++) {
                sum += nums[i];
            }
            double maxAvg = sum/k;
            int n = k;
            int i = 0;
            int j = k-1;
            while(j < len) {
                double a1 = (n > k && i >= 0) ? (sum - nums[i]*1.0)/(double)(n-1): Double.NEGATIVE_INFINITY;
                double a2 = j < len-1 ? (sum + nums[j+1]*1.0)/(double)(n+1) : Double.NEGATIVE_INFINITY;            
                if(a1 > a2) {
                    maxAvg = Math.max(maxAvg, a1);
                    sum -= nums[i]*1.0;
                    i++;
                    n--;
                } else {
                    maxAvg = Math.max(maxAvg, a2);
                    if(j<len-1) sum += nums[j+1]*1.0;
                    j++;
                    n++;
                }
            }
            return maxAvg;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.