herrDeng網內搜尋

自訂搜尋

Ads

2025年8月3日 星期日

二元搜尋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 .

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;
    }
};

沒有留言:

Related Posts Plugin for WordPress, Blogger...

熱門文章