LeetCode 644. Maximum Average Subarray II    原题链接    中等

作者： 作者的头像   wq ,  2018-05-29 21:22:35 ,  所有人可见 ,  阅读 2590

1


题目描述

一个数组长度为n，找到这个数组长度至少为k的子串的最大平均值。

样例

input [1,12,-5,-6,50,3], k = 4
Output: 12.75
Explanation:
当子串长度为4时，最大的子串和为12.75
当子串长度为5时，最大的子串和为10.8
当子串长度为6时，最大的子串和为9.16667
因此返回12.75

算法1

二分法 $O(nlogM)$ M为二分的范围

对长度至少为k的最大子串的平均值进行二分，二分的范围为start=Integer.MIN_VALUE end=Integer.MAX_VALUE，x=(start+end)/2，如果有

(nums[i]+nums[i+1]+...+nums[j])/(j-i+1)>x
=>nums[i]+nums[i+1]+...+nums[j]>x*(j-i+1)
=>(nums[i]-x)+(nums[i+1]-x)+...+(nums[j]-x)>0

则结果的范围在[x, end]，否则结果的范围为[start, x]

判断是否存在(nums[i]-x)+(nums[i+1]-x)+...+(nums[j]-x)>0可以在O(n)的时间内完成。对数组进行一次遍历，维护两个量：当前子段和cur，和当前子段前i-k个数的和pre。如果pre<0，则更新cur=cur-pre, pre=0. 每一步判断是否有cur>0，若有则返回true。

时间复杂度分析：二分的时间复杂度为O(logM)，判断是否存在某个平均值的子段的复杂度为log(n)，总时间复杂度为O(nlogM)

Java 代码

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        double s=Integer.MIN_VALUE, e=Integer.MAX_VALUE;
        while(e-s>1e-6) {
            double mid = (e+s)/2;
            if(greater(nums, k, mid)) s=mid;
            else e=mid;
        }
        return s;
    }

    public boolean greater(int[] nums, int k, double x) {
        int n = nums.length;
        double[] a = new double[n];
        for(int i=0; i<n; i++) a[i]=nums[i]-x;
        double cur=0, pre=0;
        for(int i=0; i<k; i++) cur+=a[i];
        if(cur>0) return true;
        for(int i=k; i<n; i++) {
            cur+=a[i];
            pre+=a[i-k];
            if(pre<0) {
                cur-=pre;
                pre=0;
            }
            if(cur>0) return true;
        }
        return false;
    }

}

1 评论

用户头像
JasonSun   2019-12-24 14:59         踩      回复

alternative implementation

template <class F>
struct recursive {
  F f;
  template <class... Ts>
  decltype(auto) operator()(Ts&&... ts)  const { return f(std::ref(*this), std::forward<Ts>(ts)...); }

  template <class... Ts>
  decltype(auto) operator()(Ts&&... ts)  { return f(std::ref(*this), std::forward<Ts>(ts)...); }
};

template <class F> recursive(F) -> recursive<F>;
auto const rec = [](auto f){ return recursive{std::move(f)}; };

class Solution {
 public:
  double findMaxAverage(vector<int>& nums, int k) {
    const int n = size(nums);

    auto binary_search = [&](double ll, double rr, auto target, auto f) {
      optional<double> result = std::nullopt;
      auto search = rec([&](auto&& search, double ll, double rr) -> void {
        double mid = ll + (rr - ll) / 2;
        if (std::abs(rr - ll) <= 1e-5) return;
        else if (f(mid) >= target) (result = mid, search(mid, rr));
        else if (f(mid) < target) search(ll, mid);
      });
      return search(ll, rr), result;
    };

    auto f = [&](double avg) {
      const auto centered_nums = [&](vector<double> self = {}) {
        std::transform(begin(nums), end(nums), std::back_inserter(self), [&](auto x) { return double(x) - avg; });
        return self;
      }();
      const auto prefix_sum = [&](vector<double> self = {}) {
        std::partial_sum(begin(centered_nums), end(centered_nums), std::back_inserter(self));
        return self;
      }();
      const auto prefix_sum_min = [&](vector<double> self = {}) {
        std::partial_sum(begin(prefix_sum), end(prefix_sum), std::back_inserter(self), [&](auto x, auto y) {
          return std::min(x, y);
        });
        return self;
      }();
      return [&](double acc = INT_MIN) {
        for (int i = k - 1; i < n; ++i) {
          if (i == k - 1)
            acc = std::max(acc, prefix_sum[i]);
          else
            acc = std::max({acc, prefix_sum[i], prefix_sum[i] - prefix_sum_min[i - k]});
          if (acc >= 0) break;
        }
        return acc;
      }();
    };

    const double solution = [&] {
      double ll = *min_element(begin(nums), end(nums)) - 0.0001;
      double rr = *max_element(begin(nums), end(nums)) + 0.0001;
      return *binary_search(ll, rr, 0, f);
    }();

    return solution;
  }
};