美文网首页
Maximum Average Subarray II

Maximum Average Subarray II

作者: 凡的技术园 | 来源:发表于2017-11-12 15:41 被阅读0次

    Given an array with positive and negative numbers, find the maximum average subarray which length should be greater or equal to given length k.


    思路:

    对平均值进行二分。一个数组平均的最大不会超过数组最大值,也不会低于数组最小值。也就是说,这个平均值肯定在数组最大值和最小值的范围区间内。

    用前缀和数组判断是否数组中是否有一段长度大于等于k的子数组,平均数大于等于mid。如果存在,就把left=mid,如果不存在就把right=mid。这样不断所有l和r的距离,直到重合。left 就是所能找到的最大平均值。

    复杂度:

    时间: O(nlog(max_val−min_val))O(nlog(max_val−min_val))

    空间:O(n)


    public double maxAverage(int[] nums, int k) {

           double result = 0.0;

            if(nums == null || nums.length < k) {

                 return result;

             }

             double l = Integer.MAX_VALUE;

             double r = Integer.MIN_VALUE;

             //find the largest number and smallest number in the array

              for(int i = 0; i < nums.length; i++){

                    if(nums[i] < l) {

                          l = nums[i];

                    }

                    if(nums[i] > r){

                          r = nums[i];

                   }

              }

              while(r - l >= 1e-6){

                     double mid = (l + r) / 2.0;

                    if(check_valid(nums, mid, k)){

                         l = mid;

                     }else{

                        r = mid;

                   }

            }

            return l;

         }

          private boolean check_valid(int nums[], double average, int k) {

                int n = nums.length;

                double min_pre = 0;

                double[] sum = new double[n + 1];

                sum[0] = 0;

                 for (int i = 1; i <= n; ++i) {

                 // 原数组中的每一个数减去这个mid

                      sum[i] = sum[i - 1] + nums[i - 1] - average;

                     if (i >= k && sum[i] - min_pre >= 0) {

                           return true;

                     }

                     if (i >= k)  

                             min_pre = Math.min(min_pre, sum[i - k + 1]);

              }

               return false;

      }

    相关文章

      网友评论

          本文标题:Maximum Average Subarray II

          本文链接:https://www.haomeiwen.com/subject/vuinmxtx.html