2106. Maximum Fruits Harvested After at Most K Steps
題目 :
給一個2-D array : fruits , fruits是以fruits[i][0]遞增排序
其中fruits[i][0]表示i水果的位置
fruits[i][1]表示i水果的數量
你的起始位置在startPos
可以任意變換行走的方向往右或往左
每當你到一個新的位置就可以得到該位置上所有的水果
你最多可以移動k步，請問最多可以拿到多少水果
思路 :
這題為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;
}
};

我好久沒寫扣了 哇啊啊啊啊啊