2106. 摘水果

题目链接：2106. 摘水果

方法：滑动窗口

解题思路

• 从 \(startPos\) 所能到达的最左端 \((>= startPos - k)\) 的位置 \(left\) 开始，初始化右指针 \(right = left\)，\(right\) 右移至 \(startPos\)，因为不知道继续右移能不能到达；
• 当右移超过 \(startPos\) 时，可能有两种情况：
  • \(startPos -> left -> startPos -> right\)；
  • \(startPos -> right -> startPos -> left\)；
  • 此时要判断在 \(k\) 步内能不能到达，如果不能应该将左指针右移直到可以在 \(k\) 步内到达的位置；
• 每一次右移结束，取当前最大值。

代码

class Solution {
public:
    int maxTotalFruits(vector<vector<int>>& fruits, int startPos, int k) {
        int left = lower_bound(fruits.begin(), fruits.end(), startPos - k, [](const auto &a, const int b) { return a[0] < b; }) - fruits.begin();
        int right = left, s = 0, n = fruits.size();
        for ( ; right < n && fruits[right][0] <= startPos; right ++ ) {
            s += fruits[right][1];
        }
        int ans = s;
        for ( ; right < n && fruits[right][0] <= startPos + k; right ++ ) {
            s += fruits[right][1];
            while (fruits[right][0] - fruits[left][0] * 2 + startPos > k  && 
                   fruits[right][0] * 2 - fruits[left][0] - startPos > k) {
                s -= fruits[left ++ ][1];
            }
            ans = max(ans, s);
        }
        return ans;
    }
};

复杂度分析

时间复杂度：\(O(n)\)；
空间复杂度：\(O(1)\)。