[LeetCode] 2106. Maximum Fruits Harvested After at Most K Steps

• 這一題困難的部分在於計算 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;
    }
};