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 0 ，positioni-1 滑动窗口
无论如何，最后摘到的水果一定位于区间[l, r]内，且位置l和r上都有水果。考虑区间[l, r]是如何形成的：
- 先从startPos走到l，再从l走到r，此时步数为(startPos-l)+(r-l)=startPos+r-2l。
- 先从startPos走到r，再从r走到l，此时步数为(r-startPos)+(r-l)=2r-startPos-l。
无论是上述哪种情况，当r增大时，步数必然增加，为了满足k步这一条件，l必然不可能减小，故区间具有单调性，从而可采用滑动窗口解决。窗口在移动过程中，只需要有一种情况能满足k不要求即可。
同时发现，区间[l, r]在符合条件的情况下越大越好，所以套用最大滑动窗口模板，在不满足窗口条件的情况下更新左指针，在更新左指针的循环外更新结果。
int maxTotalFruits(vector> &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] 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]对应的水果数便是一个候选答案，所有候选答案的最大值便是最终答案。
经过上面分析，需要解决两个问题
- 如果通过x和y快速确定区间[l, r] ==> 二分查找
- 如果快速求出区间[l, r]中的水果数 ==> 前缀和
由于x和y，确定其中一个，另一个就确定了，不妨枚举x，x表示在上述x和y中不带系数2的哪一个，则另一个带系数2的为(k-x)/2。
int maxTotalFruits(vector> &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 > 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)
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
