2.5 滑动窗口专题:水果成篮
1. 题目链接
leecode 904.水果成篮
2. 题目描述
给定一个整数数组 fruits
,每个元素表示一棵树上的水果类型。你只能收集两种不同类型的水果,且必须从任意位置开始按顺序连续收集。
目标:返回能收集水果的最大数量(即最长子数组长度)。
示例:
输入:fruits = [1,2,3,2,2]
输出:4
(子数组 [2,3,2,2]
,包含两种类型:2 和 3)。
作者说:
由于这里的题目比较难以理解,我给出我的理解:从数组 fruits
中找到一个最长子串,该字串中最多只有两个重复的数字。
3. 算法思路
滑动窗口法:
- 核心思想:维护一个窗口,窗口内最多包含两种不同的水果类型。
- 哈希表记录状态:用
unordered_map
统计窗口内各类型的数量。 - 动态调整窗口:
- 右指针扩展:将当前水果加入窗口。
- 左指针收缩:当窗口内类型超过 2 时,左指针右移,直到窗口合法。
- 实时更新结果:每次窗口调整后计算当前窗口长度,更新最大值。
暴力枚举法:
- 核心思想:遍历所有可能的子数组,检查是否满足最多两种类型。
- 双重循环嵌套:枚举子数组的起点
i
和终点j
。 - 类型统计:对每个子数组维护类型集合,当类型超过 2 时终止内层循环。
4. 代码实现
class Solution
{
public:
int totalFruit(vector<int>& fruits)
{
int n = fruits.size();
int left = 0, right = 0,ret = 0;
unordered_map<int,int> hash;
while(right < n)
{
// 扩展右窗口
hash[fruits[right]]++;
// 收缩左窗口
while(hash.size() > 2 )
{
hash[fruits[left]]--;
if(hash[fruits[left]] == 0)
hash.erase(fruits[left]);
left++;
}
// 更新结果
ret = max(ret, right - left + 1);
right++;
}
return ret;
}
};
5. 暴力枚举法与滑动窗口法对比图表
对比维度 | 暴力枚举法 | 滑动窗口法 |
---|---|---|
核心思想 | 遍历所有子数组,逐一检查是否包含最多两种类型。 | 动态维护窗口,保证窗口内始终包含最多两种类型。 |
时间复杂度 | O(n²)(枚举所有起点和终点,类型检查优化后为 O(n²))。 | O(n)(每个元素被左右指针各访问一次)。 |
空间复杂度 | O(1) 或 O(2)(维护一个固定大小的集合记录类型)。 | O(2)(哈希表最多存储两种类型)。 |
实现方式 | 双重循环枚举起点和终点,内层循环统计类型。 | 单层循环扩展右指针,内层循环收缩左指针。 |
适用场景 | 小规模数据(n ≤ 1e3)。 | 大规模数据(n ≤ 1e5)。 |
优点 | 逻辑简单,易于实现。 | 时间复杂度最优,适用于大规模数据。 |
缺点 | 数据规模大时性能极差(n=1e4 时需 1e8 次操作)。 | 需处理哈希表的动态更新,对边界条件敏感(如全为同一类型的数组)。 |
6. 边界条件与注意事项
- 全为一种类型:滑动窗口直接返回
n
(例如fruits = [2,2,2]
)。 - 交替类型:如
fruits = [1,2,1,2,1]
,窗口会动态调整,始终保留两种类型。 - 哈希表维护:当类型数量减到 0 时需及时删除键值,避免
hash.size()
误判。
7. 总结
- 滑动窗口法是本题的最优解,时间复杂度为 O(n),适用于大规模数据。
- 暴力枚举法仅用于验证算法正确性或处理极小数据规模。