当前位置：首页 > news >正文

滑动窗口(水果成篮)(5)

news 2026/5/12 19:34:00

https://blog.csdn.net/2601_95366422/article/details/158584220

上节课的链接

一.题目

904. 水果成篮 - 力扣（LeetCode）

二.思路讲解

2.1 审题

这道题描述的场景虽然文字较多，但核心要点其实很清晰：

你有两个篮子，每个篮子只能装同一类水果（但可以装无限个）。
你从一排果树前走过，每遇到一棵树就必须摘它的水果，并且只能放入其中一个篮子。
如果遇到一棵树的水果类型，两个篮子里都没有，那么你就必须停止。

换句话说，问题转化为：在给定的水果序列中，找到一个最长的连续子数组，使得其中包含的水果种类不超过两种。这就是经典的“最多两种不同字符的最长子串”问题，可以用滑动窗口高效解决。

2.2 思路解决

既然要用滑动窗口，我们就需要解决两个关键点：如何维护窗口内不同水果的种类数，以及如何高效地判断和更新。最直接的想法是用哈希表记录每种水果出现的次数，但考虑到题目中水果类型的范围是1 到 100000，我们可以用一个固定大小的数组来模拟哈希表，这样既简单又高效。数组的下标对应水果类型，值记录该水果在窗口内出现的次数。

接下来就是滑动窗口的标准操作：

进窗口：每次右指针向右移动，将当前水果加入窗口，对应的计数加1。
判断条件：如果窗口内不同水果的种类数超过了2，就需要出窗口，即移动左指针，将左边的水果移出窗口，同时将其计数减1；若某个水果的计数减到0，则种类数减少。
更新结果：在每次调整后，当窗口内种类数不超过2时，记录当前窗口的长度，并更新最大值。

三.代码演示

class Solution { public: int totalFruit(vector<int>& fruits) { int nums[100001] = {0};//数组，去重的 int basket = 0;//篮子计数器 int n = fruits.size(); int len = 0; for(int left = 0,right = 0;right < n;right++) { nums[fruits[right]]++;//进窗口 //篮子被用了 if(nums[fruits[right]] == 1) basket++; //判断条件 while(left < right && basket > 2) { nums[fruits[left]]--; if(nums[fruits[left]] == 0) basket--; left++; } len = max(len,right - left + 1); } return len; } };

四.代码讲解

第一步：初始化辅助数组和变量
定义一个大小为100001的整型数组nums，并将所有元素初始化为 0。这个数组用于记录每种水果在当前窗口中出现的次数，因为题目给出的水果类型范围是 1 到 100000，所以数组大小足够。
定义变量basket用于统计当前窗口中不同水果的种类数，初始值为 0。
获取数组长度n = fruits.size()，定义变量len用于存储最长连续子数组的长度，初始值为 0。同时初始化左指针left = 0和右指针right = 0。

第二步：遍历数组，移动右指针（进窗口）
使用for循环，让右指针right从 0 到n-1依次遍历。每次循环执行以下操作：

将当前右指针指向的水果fruits[right]在数组nums中的计数加 1，即nums[fruits[right]]++，表示该水果进入窗口。
如果该水果的计数在加 1 后等于 1（即之前窗口中没有这种水果），则将basket加 1，表示新增加了一种水果种类。

第三步：判断窗口内水果种类是否超过 2
如果当前basket > 2，说明窗口中包含了三种或以上的不同水果，需要收缩左边界（出窗口）来减少种类数。
在while (left < right && basket > 2)循环中执行以下操作：

将左指针指向的水果fruits[left]在数组nums中的计数减 1，即nums[fruits[left]]--，表示该水果移出窗口。
如果该水果的计数在减 1 后等于 0，说明窗口中已经没有这种水果了，则将basket减 1，表示种类数减少。
将左指针left向右移动一位（left++），继续检查是否仍超过 2 种。

第四步：更新最长长度
当窗口内水果种类不超过 2 时（即退出while循环后），计算当前窗口的长度right - left + 1，并用它更新len，取较大值：len = max(len, right - left + 1)。这一步记录下当前满足条件的最长窗口长度。

第五步：返回结果
遍历结束后，len中存储的就是可以摘到的最大水果数量（即最长连续子数组的长度），将其返回。

重点总结

核心数据结构：一个固定大小的数组nums充当哈希表，高效记录每种水果的出现次数。
关键变量basket实时统计窗口内不同水果的种类数。
滑动窗口的四个动作：进窗口（右移并更新计数和种类）、判断条件（种类是否超过 2）、出窗口（左移并更新计数和种类）、更新结果（记录当前最长长度）。
整个过程只遍历数组一次，时间复杂度O(n)，空间复杂度O(1)（因为数组大小固定）。