摘水果二分前缀和

题目链接：https://leetcode.cn/problems/maximum-fruits-harvested-after-at-most-k-steps/description/?envType=daily-question&envId=2025-08-03

题目

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

另给你两个整数 startPos 和 k 。最初，你位于 startPos 。从任何位置，你可以选择向左或者向右走。在 x 轴上每移动一个单位，就记作一步。你总共可以走最多 k 步。你每达到一个位置，都会摘掉全部的水果，水果也将从该位置消失（不会再生）。

返回你可以摘到水果的最大总数

分析

由于我们的起点是固定的，反向无非是往左走或者是往右走，只需要保证步数之和等于 k 即可。

情况 1：先往左走 x步，再往右走 k - x 步

此时总共走的路径为：x + (k - x) = k

最终能覆盖的坐标范围是：

向左走 x步：到达 startPos- x
向右走 (k - x) 步：最终最大右移量 = (k - x) - x = k - 2x

情况 2：先往右走 x 步，再往左走 k - x 步

此时总共也是走 k 步。

最终能覆盖的坐标范围是：

向右走 x 步：到达 startPos + x
再向左走 (k - x) 步，最大左移量为 x - (k - x) = 2x - k

📌 归纳

对于每个，你需要枚举两个移动区间：

情况 1（先左后右）：

$区间$

情况 2（先右后左）：

$区间$

最后我们根据fruits数组得到关于水果数量的前缀和，对每次求值求最大值即可得到最大水果数。

代码

/**
 * @param {number[][]} fruits
 * @param {number} startPos
 * @param {number} k
 * @return {number}
 */
var maxTotalFruits = function(fruits, startPos, k) {
    const n = fruits.length;
    const sum = new Array(n + 1).fill(0);
    const indices = new Array(n).fill(0);
    sum[0] = 0;
    for(let i = 0;i < n;i++){
        sum[i + 1] = sum[i] + fruits[i][1];
        indices[i] = fruits[i][0];
    }

    let ans = 0;
    for(let x = 0;x <= Math.floor(k / 2);x++){
        /* 向左走 x 步，再向右走 k - x 步 */
        let y = k - 2*x;
        let left = startPos - x;
        let right = startPos + y;
        let start = lowerBound(indices,0,n - 1,left);
        let end = upperBound(indices,0,n - 1,right);
        ans = Math.max(ans,sum[end] - sum[start])
        /* 向右走 x 步，再向左走 k - x 步 */
        y = k - 2 * x;
        left = startPos - y;
        right = startPos + x;
        start = lowerBound(indices, 0, n - 1, left);
        end = upperBound(indices, 0, n - 1, right);
        ans = Math.max(ans, sum[end] - sum[start]);
    }
    return ans;
};

const lowerBound = (arr, left, right, val) => {
    let res = right + 1;
    while (left <= right) {
        const mid = left + Math.floor((right - left) / 2);
        if (arr[mid] >= val) {
            res = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return res;
}
const upperBound = (arr, left, right, val) => {
    let res = right + 1;
    while (left <= right) {
        const mid = left + Math.floor((right - left) / 2);
        if (arr[mid] > val) {
            res = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return res;
};