关于算法:每日一题摘水果

2106. 摘水果

关键词：滑动窗口、二分查找、前缀和

题目起源：2106. 摘水果 – 力扣（Leetcode）

题目形容

 T 滑动窗口
 T 二分查找
 T 前缀和

在一个有限的 x 坐标轴上，有许多水果散布在其中某些地位。给你一个二维整数数组 fruits，其中 fruits[i] = [positioni, amounti] 示意共有 amounti 个水果搁置在 positioni 上。fruits 曾经按 positioni 升序排列 ，每个 positioni 互不雷同。

另给你两个整数 startPos 和 k。最后，你位于 startPos。从任何地位，你能够抉择 向左或者向右 走。在 x 轴上每挪动 一个单位 ，就记作 一步 。你总共能够走 最多 k 步。你每达到一个地位，都会摘掉全副的水果，水果也将从该地位隐没（不会再生）。

返回你能够摘到水果的 最大总数。

输出：fruits = [[2,8],[6,3],[8,6]], startPos = 5, k = 4
输入：9

输出：fruits = [[0,9],[4,1],[5,7],[6,2],[7,4],[10,9]], startPos = 5, k = 4
输入：14

输出：fruits = [[0,3],[6,4],[8,5]], startPos = 3, k = 2
输入：0

数据范畴
1 <= fruits.length <= 105
fruits[i].length == 2
0 <= startPos, positioni <= 2 * 105
对于任意 i > 0，positioni-1 < positioni 均成立（下标从 0 开始计数）1 <= amounti <= 104
0 <= k <= 2 * 105

滑动窗口

无论如何，最初摘到的水果肯定位于区间 [l, r] 内，且地位 l 和 r 上都有水果。思考区间 [l, r] 是如何造成的：

1. 先从 startPos 走到 l，再从 l 走到 r，此时步数为(startPos-l)+(r-l)=startPos+r-2l。
2. 先从 startPos 走到 r，再从 r 走到 l，此时步数为(r-startPos)+(r-l)=2r-startPos-l。

无论是上述哪种状况，当 r 增大时，步数必然减少，为了满足 k 步这一条件，l 必然不可能减小，故区间具备枯燥性，从而可采纳滑动窗口解决。窗口在挪动过程中，只须要有一种状况能满足 k 不要求即可。

同时发现，区间 [l, r] 在符合条件的状况下越大越好，所以套用最大滑动窗口模板，在不满足窗口条件的状况下更新左指针，在更新左指针的循环外更新后果。

int maxTotalFruits(vector<vector<int>> &fruits, int startPos, int k) {

    auto &f = fruits;

    // 找到第一个符合条件的窗口的左边界
    int l = lower_bound(f.begin(), f.end(), startPos - k, [](const auto &v, int p) {return v[0] < p;
    }) - f.begin();
    int r = l, cnt = 0, n = f.size();
    // 第一个符合条件的窗口的右边界为 startPos，窗口内水果数量为 cnt
    for (; r < n && f[r][0] <= startPos; r++)cnt += f[r][1];

    // 窗口滑动
    int res = cnt;
    for (; r < n && f[r][0] <= startPos + k; r++) {
        // 更新窗口内的水果数
        cnt += f[r][1];
        // 不满足窗口条件的状况下更新左指针
        while (f[r][0] * 2 - f[l][0] - startPos > k &&
                f[r][0] + startPos - f[l][0] * 2 > k
                )
            cnt -= f[l++][1];
        // 更新左指针的循环外更新后果
        res = max(cnt, res);
    }

    return res;
}

工夫复杂度：O(n)

空间复杂度：O(1)

前缀和 + 二分

无论如何，最初摘到的水果肯定位于区间 [l, r] 内，无妨设 l 距 startPos 有 x 步，r 距 startPos 有 y 步，则

• 若先从 startPos 走到 l，再从 l 走到 r，则步数为 2x+y
• 若先从 startPos 走到 r，再从 r 走到 l，则步数为 2y+x

因为 x 和 y 的最大值均为 k，最小值均为 0，且确定其中一个，另一个就确定了，于是，无妨枚举每一对 x、y，对于每一对 x、y，都有与之对应的区间 [l, r]，区间[l, r] 对应的水果数便是一个候选答案，所有候选答案的最大值便是最终答案。

通过下面剖析，须要解决两个问题

1. 如果通过 x 和 y 疾速确定区间[l, r] ==> 二分查找
2. 如果疾速求出区间 [l, r] 中的水果数 ==> 前缀和

因为 x 和 y，确定其中一个，另一个就确定了，无妨枚举 x，x 示意在上述 x 和 y 中不带系数 2 的哪一个，则另一个带系数 2 的为(k-x)/2。

int maxTotalFruits(vector<vector<int>> &fruits, int startPos, int k) {

    auto &f = fruits;
    int n = f.size();

    // 预处理前缀和与水果地位
    int s[n + 1], p[n];
    for (int i = s[0] = 0; i < n; i++)
        s[i + 1] = f[i][1] + s[i], p[i] = f[i][0];

    // 枚举 x 和 y
    int res = 0;
    for (int x = k, y, l, r; ~x; x--) {y = (k - x) >> 1;
        // 先左后右
        l = lower_bound(p, p + n, startPos - y) - p;
        r = upper_bound(p, p + n, startPos + x) - p;
        res = max(s[r] - s[l], res);
        // 先右后左
        l = lower_bound(p, p + n, startPos - x) - p;
        r = upper_bound(p, p + n, startPos + y) - p;
        res = max(s[r] - s[l], res);
    }
    
    return res;
}

二分查找时须要留神，因为前缀和数组下标从 1 开始，设 x 和 y 对应的理论区间为[tl, tr]，tl、tr 也从 1 开始，则，lower_bound 找到是 tl-1，upper_bound 找到是 tr。

工夫复杂度：O(klog(n))

空间复杂度：O(n)