滑动窗口：摘水果问题

• 题目描述
• 示例&提示
• 题目分析
• 算法分析
• • 算法选择分析
  • 算法过程分析
  • 算法复杂度分析
• 测试案例
• 完整代码

在一个无限的 X 坐标轴上，有许多水果分布在其中某些位置。给你一个二维整数数组 fruits ，其中 fruits[i] = [position_i, amount_i] 表示共有 amount_i 个水果放置在 position_i 上。fruits 已经按 position_i 升序排列 ，每个 position_i 互不相同 。
另给你两个整数 startPos 和 k 。最初，你位于 startPos 。从任何位置，你可以选择 向左或者向右 走。在 X 轴上每移动 一个单位 ，就记作 一步 。你总共可以走 最多 k 步。你每达到一个位置，都会摘掉全部的水果，水果也将从该位置消失（不会再生）。
返回你可以摘到水果的 最大总数 。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/maximum-fruits-harvested-after-at-most-k-steps
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

示例1：

输入：fruits = [[2,8],[6,3],[8,6]], startPos = 5, k = 4
输出：9
解释：
最佳路线为：
- 向右移动到位置 6 ，摘到 3 个水果
- 向右移动到位置 8 ，摘到 6 个水果
移动 3 步，共摘到 3 + 6 = 9 个水果

示例2：

输入：fruits = [[0,9],[4,1],[5,7],[6,2],[7,4],[10,9]], startPos = 5, k = 4
输出：14
解释：可以移动最多 k = 4 步，所以无法到达位置 0 和位置 10 。
最佳路线为：
- 在初始位置 5 ，摘到 7 个水果
- 向左移动到位置 4 ，摘到 1 个水果
- 向右移动到位置 6 ，摘到 2 个水果
- 向右移动到位置 7 ，摘到 4 个水果
移动 1 + 3 = 4 步，共摘到 7 + 1 + 2 + 4 = 14 个水果

示例3：

输入：fruits = [[0,3],[6,4],[8,5]], startPos = 3, k = 2
输出：0
解释：最多可以移动 k = 2 步，无法到达任一有水果的地方

提示：

■ 1 < = f r u i t s . l e n g t h < = 1 0 5 1 <= fruits.length <= 10^5 1<=fruits.length<=105
■ f r u i t s [ i ] . l e n g t h = = 2 fruits[i].length == 2 fruits[i].length==2
■ 0 < = s t a r t P o s , p o s i t i o n i < = 2 ∗ 1 0 5 0 <= startPos, position_i <= 2 * 10^5 0<=startPos,positioni​<=2∗105
■ 对 于 任 意 i > 0 ， p o s i t i o n i − 1 < p o s i t i o n i 均 成 立 （ 下 标 从 0 开 始 计 数 ） 对于任意 i > 0 ，position_{i-1} < position_i 均成立（下标从 0 开始计数） 对于任意i>0，positioni−1​ ■ 1 < = a m o u n t i < = 1 0 4 1 <= amount_i <= 10^4 1<=amounti​<=104
■ 0 < = k < = 2 ∗ 1 0 5 0 <= k <= 2 * 10^5 0<=k<=2∗105

根据题目描述，在已知出发位置startPos、从该点出发（可以向左或者向右走）采摘水果总共可以走的步数k的情况下，希望可以采摘到最大总数的水果。同时每到达1个位置，就会摘掉该位置的全部水果。我们可以尝试采用滑动窗口算法，思考在既定最大步数k的情况下，确定某个区间，若采摘区间内的水果需要的步数不超过最大步数k，则该区间为可行窗口；若某个可行窗口内可以采摘到水果的总数最大时，则该区间为最佳窗口。
首先，我们定义左指针left和右指针right两个指针确定窗口的左右边界，即确定初始窗口；计算滑动窗口区间采摘水果所需最小步数：

■ 如果滑动窗口区间所需最小步数大于k且窗口长度大于1，则需要收缩窗口；
■ 如果滑动窗口区间所需最小步数大于k且窗口长度等于1，则需要整体滑动窗口，即同时移动左右指针；
■ 如果滑动窗口区间所需最小步数小于等于k，则需要扩张窗口。

滑动窗口，本质是双指针法中的对撞指针（左右指针）法，可以理解成是可以左右滑动的窗口，每次滑动都会记录下当前窗口的状态，再找出符合条件的适合的窗口。它可以将双层嵌套的循环问题，转换为单层遍历的循环问题。算法使用左指针left和右指针right两个指针构成窗口，可以将二维循环的问题转化成一维循环一次遍历，使得时间复杂度从 O ( n 2 ) O(n^2) O(n2)降低至 O ( n ) O(n) O(n)，常见的有经典字符串查找算法Rabin-Karp指纹字符串查找算法，它本质上也使用了滑动窗口的思想，通过公式推导降低窗口滑动时计算子串哈希值的复杂度。

（1） 初始化（以示例2为例）：

（2） 当前窗口区间所需最小步数大于k且窗口长度等于1，需要整体滑动窗口：

（3） 当前窗口区间所需最小步数小于k，需要扩张窗口：

（4） 当前窗口区间所需最小步数小于k，需要扩张窗口：

（5） 当前窗口区间所需最小步数小于k，需要扩张窗口：

（6） 当前窗口区间所需最小步数小于k，需要扩张窗口：

（7） 当前窗口区间所需最小步数大于k且窗口长度大于1，需要收缩窗口：

（8） 当前窗口区间所需最小步数大于k且窗口长度大于1，需要收缩窗口：

（9） 当前窗口区间所需最小步数大于k且窗口长度大于1，需要收缩窗口：

（10） 当前窗口区间所需最小步数大于k且窗口长度大于1，需要收缩窗口：

（11） 当前窗口区间所需最小步数大于k且窗口长度等于1，需要整体滑动窗口：

（12） 此时右指针right以超出范围，程序结束：

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

测试案例1：

输入：fruits = [[2,8],[6,3],[8,6]],startPos = 5,k = 4
输出：9

测试案例2

输入：fruits = [[0,9],[4,1],[5,7],[6,2],[7,4],[10,9]],startPos = 5,k = 4
输出：14

测试案例2

输入：fruits = [[0,3],[6,4],[8,5]],startPos = 3,k = 2
输出：0

C++ 代码实现

#include 
#include 
#include 
#include 
int cost(int lower, int upper, int startPos) {
	return std::min(abs(startPos - lower), abs(startPos - upper)) + upper - lower;
}

int maxTotalFruits(std::vector>& fruits, int startPos, int k) {
	int left = 0, right = 0;
	int winSum = 0, ans = 0;
	while (left < fruits.size()) {
		winSum += fruits[right][1];
		while (cost(fruits[left][0], fruits[right][0], startPos) > k and left < right) {
			winSum -= fruits[left][1];
			left += 1;
		}
		if (cost(fruits[left][0], fruits[right][0], startPos) > k) {
			winSum -= fruits[left][1];
			right += 1;
			left += 1;
		} else {
			ans = std::max(ans, winSum);
			right += 1;
		}
	}
	return ans;
}

int main() {
	std::vector> fruits;
	std::vector fruit;
	int temp;
	int startPos, k;
	std::cout << "请输入草莓数据（格式：草莓位置，草莓数量，以空格隔开），回车结束：" << std::endl;
	while (1) {
		fruit.clear();
		for (int i = 0; i < 2; i++) {
			std::cin >> temp;
			fruit.push_back(temp);
		}
		fruits.push_back(fruit);
		if (std::cin.get() == 'n') break;
	}
	std::cout << "请输入起点位置：";
	std::cin >> startPos;
	std::cout << "请输入最大步数：";
	std::cin >> k;
	std::cout << "最大可以摘到的草莓数量：";
	std::cout << maxTotalFruits(fruits, startPos, k);
	system("pause");
	return 0;
}

C++ 运行结果

Python 代码实现

def maxTotalFruits(fruits, startPos, k) -> int:
    def cost(lower, upper):
        # 以startPos为起点，走完[lower,upper]区间所需的最小步数
        return min(abs(startPos - lower), abs(startPos - upper)) + upper - lower

    # 滑动窗口区间[left,right]，winSum为区间内的草莓总数
    left, right, winSum = 0, 0, 0
    ans = 0
    while right < len(fruits):
        winSum += fruits[right][1]
        # 如果滑动窗口区间所需最小步数大于k且窗口长度大于1 收缩窗口
        while cost(fruits[left][0], fruits[right][0]) > k and left < right:
            winSum -= fruits[left][1]
            left += 1
        # 如果滑动窗口区间所需最小步数大于k且窗口长度等于1 整体滑动窗口
        if cost(fruits[left][0], fruits[right][0]) > k:
            # 左右指针要同时移动
            winSum -= fruits[left][1]
            right += 1
            left += 1
        # 如果滑动窗口区间所需最小步数小于等于k
        else:
            # 如果滑动窗口区间内的草莓总数大于ans，则更新ans
            ans = max(ans, winSum)
            # 右指针移动 扩张窗口
            right += 1
    return ans


if __name__ == '__main__':
    fruits = []
    # 输入草莓数据
    while True:
        fruit = input('请输入草莓数据（格式：草莓位置，草莓数量，以空格隔开），双击回车结束：').split()
        if not fruit:
            break
        fruits.append([int(fruit[0]), int(fruit[1])])
    # 输入起点位置
    startPos = int(input('请输入起点位置：'))
    # 输入行进步长
    k = int(input('请输入最大步数：'))
    print('最大可以摘到的草莓数量：', maxTotalFruits(fruits, startPos, k))

Python 运行结果