- 這一題困難的部分在於計算 windows size
- 我的作法是根據
startPos + i
來計算左指針,左指針位置會在 startPos - max(k - 2*i, (k - i) / 2)
,也就是算出左邊來回或是右邊來回兩種情況下, windowSize 最大的可能。
class Solution {
public:
int maxTotalFruits(vector<vector<int>>& fruits, int startPos, int k) {
sort(fruits.begin(), fruits.end());
int curr = 0;
int j = 0;
while (j < fruits.size() && fruits[j][0] < startPos - k) j++;
int u = j;
for (int i = startPos - k; i <= startPos && j < fruits.size(); i++) {
if (fruits[j][0] == i) curr += fruits[j++][1];
}
if (j == fruits.size()) return curr;
int res = curr;
int left = startPos - k;
for (int i = 1; i <= k && j < fruits.size(); i++) {
int right = startPos + i;
int pos = startPos - max(k - 2*i, (k - i)/2);
if (fruits[j][0] == right) curr += fruits[j++][1];
while (left < pos) {
if (fruits[u][0] == left++) curr -= fruits[u++][1];
}
res = max(res, curr);
}
return res;
}
};