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

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(vectorint 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)因为数组大小固定。