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 <= 105fruits[i].length == 20 <= startPos, positioni <= 2 * 105对于任意 i > 0 ，positioni-1 < positioni 均成立（下标从 0 开始计数）1 <= amounti <= 1040 <= k <= 2 * 105滑动窗口
无论如何，最初摘到的水果肯定位于区间[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<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]对应的水果数便是一个候选答案，所有候选答案的最大值便是最终答案。
通过下面剖析，须要解决两个问题
- 如果通过x和y疾速确定区间[l, r] ==> 二分查找
- 如果疾速求出区间[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)