力扣2106.摘水果
力扣2106.摘水果
-
在下标上做滑窗
- 二分出左边最远能取到的点j
- 自己写lowerbound
- (j,start)这个区间的水果数就是初值
- 二分出左边最远能取到的点j
-
如何判断一个区间是否合法
- 先往右走再往左走：fruit(right,0) - start + fruit(right,0) - fruit(left,0);
- 先往左走再往右走：start - fruit(left,0) + fruit(right,0) - fruit(left,0);
-
class Solution {public:int maxTotalFruits(vector<vector<int>>& fruits, int startPos, int k) {int j = lowerBound(fruits,startPos-k);int res=0,sum=0,i=j,n=fruits.size();for(;i<n && fruits[i][0] <= startPos;i++) sum +=fruits[i][1];res=sum;for(;i<n && fruits[i][0] <= startPos + k;i++){sum += fruits[i][1];while(fruits[i][0] * 2 - fruits[j][0] - startPos > k && fruits[i][0] - fruits[j][0] * 2 + startPos > k)sum -= fruits[j++][1];res = max(res,sum);}return res;}int lowerBound(vector<vector<int>> fruits,int target){int l = 0 , r = fruits.size();while(l < r){int mid = l + r >> 1;if(fruits[mid][0] < target) l = mid + 1;else r = mid;}return r;}};