2106. Maximum Fruits Harvested After at Most K Steps
思路:
这题为sliding windows
假设要取得fruits[start]到fruits[end]这两点间的水果
有分两种走法
先往左再往右花费步数为 : fruits[end][0] + startPos - 2*fruits[start][0]
先往右再往走花费步数为 : 2*fruits[end][0] - startPos - fruits[start][0]
就先找出fruits中位置在[startPos-k, startPos+k]范围内的点
接着从最左边的点开始走
并且判断上面两种走法中的最小步数是否大于k
是的话就移动start，一直到小于k为止
就这样一直纪录最大获得的水果数量
就能得到答案了
c++ code :
class Solution {
public:
int maxTotalFruits(vector<vector<int>> &fruits, int startPos, int k)
{
int start = 0, n = fruits.size(), sum = 0, ans = 0;
while (start < n && fruits[start][0] < startPos - k) {
start++;
}
for (int end = start; end < n && fruits[end][0] <= startPos + k; end++
) {
sum += fruits[end][1];
while (min(fruits[end][0] - 2 * fruits[start][0] + startPos,
2 * fruits[end][0] - fruits[start][0] - startPos) > k)
{
sum -= fruits[start][1];
start++;
}
ans = max(ans, sum);
}
return ans;
}
};

吃饭了 别卷了