二元搜尋sliding window C++ py3解Leetcode 2106難題Maximum Fruits Harvested After ...

二元搜尋sliding window cpp py3解Leetcode 2106難題Maximum Fruits Harvested After at Most K Steps

[C++ solution請進]

---

Use binary search to shrink the moving indices. Define the step function, then proceed the standard sliding window .

[codes on Leetcode]https://leetcode.com/problems/maximum-fruits-harvested-after-at-most-k-steps/solutions/7037701/binary-search-then-sliding-window-c-beats-100-py3/

[Sliding window/2-pointer playlist]https://www.youtube.com/watch?v=pi1XpQU_Yxo&list=PLYRlUBnWnd5KrCfs7qCFb-Bvn7dvnakFy

class Solution {
public:
    int step(int R, int L, int startPos) {// goes left then right but also right then left
        return min(startPos-2*L+R, 2*R-startPos-L);// both should > k
    }
    
    int maxTotalFruits(vector<vector<int>>& fruits, int startPos, int k) {
        int i0=lower_bound(fruits.begin(), fruits.end(), vector<int>(1,startPos-k))-fruits.begin();
        int iN=upper_bound(fruits.begin()+i0, fruits.end(), vector<int>(1,startPos+k+1))-fruits.begin();

        int ans=0, wsum=0;
        for (int l=i0, r=i0; r<iN; k){
                wsum-=fruits[l][1];
                l++;
            }
            ans=max(ans, wsum);
        }
        return ans;
    }
};