算法基础算法

实数值域二分

字数统计: 1k字   |   阅读时长: 4分
,

摘要: 实数值域二分经典题目 lc644

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在文章 二分 中，我们总结了二分的常见类型，其中主要是区间二分以及值域二分。

在文章 实数区间二分 中，我们学习了实数的区间二分，本文我们了解一下实数值域二分。

首先回顾一下值域二分，很多问题中我们要求某个指标能取到的最大值，但有时候直接求指标的最大值不好求，但是如果给定一个值 y，判定是否存在某种方式使得所求指标能取到 y 是容易做的；并且所求的指标具有单调性：y 判定成功，则大于/小于 y 的值也会判定成功。则我们可以应用以下值域二分算法：

对值域 [l, r] 的中点 mid 进行判定，如果 check(mid) 成功，则区间变为 [mid, right]，若不成功，则区间变为 [left, mid - 1]。

实数值域二分的思路与上面差不多，只是值域 [l, r] 是实数。下面我们看一道实数值域二分的经典问题。

题目

给定一个包含 n 个整数的数组，找到最大平均值的连续子序列，且长度大于等于 k。并输出这个最大平均值。

提示:

1
2
3
1 <= k <= n <= 10000。
数组中的元素范围是 [-10000, 10000]。
答案的计算误差小于 1e-5 。

样例 1:
输入: [1,12,-5,-6,50,3], k = 4
输出: 12.75
解释:
当长度为 5 的时候，最大平均值是 10.8，
当长度为 6 的时候，最大平均值是 9.16667。
所以返回值是 12.75。

题解

算法: 实数值域二分

二分地在答案范围 [left, right] 猜一个平均值 mid，然后回答提问: 

1
nums 上是否存在一个长度大于等于 k 的区间，其平均值大于等于 mid

相当于问是否存在某个长度 l >= k 并且以 i 结尾的子区间 nums[i-l+1..i]

1
sum(nums[i-l+1..i])/l >= mid

将不等式变形

1
2
sum(nums[i-l+1..i]) - l * mid >= 0
sum(nums[j] - mid) >= 0, 其中 i - l + 1 <= j <= i

于是提问变成了：是否存在某个长度 l >= k 并且以 i 结尾的子区间 nums[i-l+1..i]，在区间 i-l+1 <= j <= i 上 nums[j] - mid 的和大于等于 0.

枚举 i = k-1..n-1，问：以 i 结尾的长度大于等于 k 的区间是否有和 >= 0 的。

这一问只跟 i 前面的某些信息有关。用两个变量维护相关的信息

1
2
sum := 区间 i-k+1 <= j <= i 上，nums[j]-mid 的和
prev := 以 i-k 结尾的最大 nums[j]-mid 的和

枚举到 i 的时候，首先更新信息

1
2
3
sum -= nums[i - k];
sum += nums[i];
prev = max(prev + nums[i - k] - mid, nums[i - k] - mid);

然后检查，如果 sum + max(0, prev) >= 0 则检查通过，找到了以 i 结尾的长度大于等于 k 的区间满足条件了，返回 true，否则继续枚举 i。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
public:
    double findMaxAverage(vector<int>& nums, int k) {
        int minx = nums[0], maxx = nums[0];
        for(int i: nums)
        {
            minx = min(minx, i);
            maxx = max(maxx, i);
        }
        double left = minx, right = maxx;
        while(left + EPS < right)
        {
            double mid = (left + right) / 2;
            if(check(nums, mid, k))
                left = mid;
            else
                right = mid;
        }
        return left;
    }

private:
    const double EPS = 1e-7;

    bool check(const vector<int>& nums, double mid, const int k)
    {
        int n = nums.size();
        double sum = 0.0;
        double prev = 0.0;
        for(int i = 0; i < k; ++i)
        {
            sum += nums[i] - mid;
        }
        if(sum + EPS > 0)
            return true;
        for(int i = k; i < n; ++i)
        {
            sum -= nums[i - k];
            sum += nums[i];
            prev = max(prev + nums[i - k] - mid, nums[i - k] - mid);
            if(sum + max(0.0, prev) + EPS > 0)
                return true;
        }
        return false;
    }
};
Share