首页 > 分享 > 【LeetCode】滑动窗口

【LeetCode】滑动窗口

花匠小妙招
2025-11-23 05:07

前言

本文介绍了一个滑动窗口算法解决LeetCode 904题"水果成篮"问题。

题目链接：904.水果成篮

题目描述

你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果种类。

你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：

你只有两个篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。你可以选择任意一棵树开始采摘，你必须从每棵树（包括开始采摘的树）上 恰好摘一个水果。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。

给你一个整数数组 fruits ，返回你可以收集的水果的最大数目。

示例 1：

输入： fruits = [1,2,1]
输出： 3
解释： 可以采摘全部 3 棵树。

示例 2：

输入： fruits = [0,1,2,2]
输出： 3
解释： 可以采摘 [1,2,2] 这三棵树。
如果从第一棵树开始采摘，则只能采摘 [0,1] 这两棵树。

示例 3：

输入： fruits = [1,2,3,2,2]
输出： 4
解释： 可以采摘 [2,3,2,2] 这四棵树。
如果从第一棵树开始采摘，则只能采摘 [1,2] 这两棵树。

示例 4：

输入： fruits = [3,3,3,1,2,1,1,2,3,3,4]
输出： 5
解释： 可以采摘 [1,2,1,1,2] 这五棵树。

提示：

1 <= fruits.length <= 10^5
0 <= fruits[i] < fruits.length

算法原理

这道题虽然看起来说得很复杂，但读完题之后我们其实可以用一句话总结就是：在给定的数组中找出一个最长的子数组，要求子数组中只能出现两种不同的数字，然后返回子数组的长度即可。

这样的话这道题就变得简单了，我们可以通过给出的示例再来理解一下题目的意思，比如示例4 中：

fruits = [3,3,3,1,2,1,1,2,3,3,4]

我们要找的子数组是 [1,2,1,1,2] ，很直观就能看出来，我们要找的是一段连续的子区间，所以这道题我们可以试着用滑动窗口来做。

道友们也可以先用一个示例在画图板上模拟一遍滑动窗口的过程。

因为我们在模拟的时候肯定知道区间里面到底有几种不同的数字，但是写程序的时候它又不知道，所以我们这里还要记录一下区间中不同的数字种类以及出现的次数，我们这里就定义四个变量来存一下。

我们就以示例4 为例，定义两个指针 left 和 right ，先是进窗口，我们让 right++，然后是判断区间中数字的种类是否超过了 2，更新那 4 个变量，如果超过了，就循环出窗口，出完窗口之后我们最后更新区间的长度，等循环结束即遍历完数组之后，我们返回最后的结果。

代码实现

class Solution { public: int totalFruit(vector<int>& fruits) { int left = 0, right = 0, len = 0; int a = -1, sizea = 0, sizeb = 0, b = -1; while (right < fruits.size()) { if (a == -1) a = fruits[right], sizea++; else if (a == fruits[right]) sizea++; if (b == -1 && a != fruits[right]) b = fruits[right], sizeb++; else if (b == fruits[right]) sizeb++; while (fruits[right] != a && fruits[right] != b) { if (fruits[left] == a) { sizea--; if (sizea == 0) { a = -1; a = fruits[right]; sizea++; } } else { sizeb--; if (sizeb == 0) { b = -1; b = fruits[right]; sizeb++; } } left++; } len = max(len, sizea + sizeb); right++; } return len; } };

cpp

运行

123456789101112131415161718192021222324252627282930313233343536373839404142434445

我们这里是定义了 a 和 b 两个变量来统计数字种类，再定义了两个变量 sizea 和sizeb 分别记录 a 和 b 两个数字出现的次数，最后区间长度更新结果时也是 sizea + sizeb。
我们可以提交一下看看
在这里插入图片描述
虽然代码写的有点拉跨，但是能提交通过，说明我们分析算法原理是没问题的，道友们也可以做一做，有更好的写法欢迎在评论区交流！