二元搜尋sliding window cpp py3解Leetcode 2106難題Maximum Fruits Harvested After at Most K Steps
---
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; } };
沒有留言:
張貼留言