当前位置: 首页 > article >正文

2.5 滑动窗口专题:水果成篮

1. 题目链接

leecode 904.水果成篮


2. 题目描述

给定一个整数数组 fruits,每个元素表示一棵树上的水果类型。你只能收集两种不同类型的水果,且必须从任意位置开始按顺序连续收集。
目标:返回能收集水果的最大数量(即最长子数组长度)。
示例
输入:fruits = [1,2,3,2,2]
输出:4(子数组 [2,3,2,2],包含两种类型:2 和 3)。
作者说:
由于这里的题目比较难以理解,我给出我的理解:从数组 fruits 中找到一个最长子串,该字串中最多只有两个重复的数字。


3. 算法思路

滑动窗口法

  1. 核心思想:维护一个窗口,窗口内最多包含两种不同的水果类型。
  2. 哈希表记录状态:用 unordered_map 统计窗口内各类型的数量。
  3. 动态调整窗口
    • 右指针扩展:将当前水果加入窗口。
    • 左指针收缩:当窗口内类型超过 2 时,左指针右移,直到窗口合法。
  4. 实时更新结果:每次窗口调整后计算当前窗口长度,更新最大值。

暴力枚举法

  1. 核心思想:遍历所有可能的子数组,检查是否满足最多两种类型。
  2. 双重循环嵌套:枚举子数组的起点 i 和终点 j
  3. 类型统计:对每个子数组维护类型集合,当类型超过 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. 边界条件与注意事项
  1. 全为一种类型:滑动窗口直接返回 n(例如 fruits = [2,2,2])。
  2. 交替类型:如 fruits = [1,2,1,2,1],窗口会动态调整,始终保留两种类型。
  3. 哈希表维护:当类型数量减到 0 时需及时删除键值,避免 hash.size() 误判。

7. 总结
  • 滑动窗口法是本题的最优解,时间复杂度为 O(n),适用于大规模数据。
  • 暴力枚举法仅用于验证算法正确性或处理极小数据规模。

http://www.kler.cn/a/587203.html

相关文章:

  • 996引擎-问题处理:缺失特效分割文件 ModelAtlasSplitConfigs
  • MAC安装logisim教程(新手级详细教程)
  • 机器学习——正则化、欠拟合、过拟合、学习曲线
  • 智能语音对话小程序功能优化day2-语音输入
  • TensorFlow 是什么?
  • 界面组件DevExpress WPF中文教程:Grid - 如何显示嵌套栏(Bands)?
  • 蓝桥杯 17110抓娃娃
  • 【SpringMVC】常用注解:@CookieValue
  • synchronized与 Java内置锁(未写完)
  • 《TCP/IP网络编程》学习笔记 | Chapter 18:多线程服务器端的实现
  • 《Electron 学习之旅:从入门到实践》
  • RK3588 openssl-3.4.1 编译安装
  • unity生命周期
  • vue埋点
  • Python实现NOA星雀优化算法优化随机森林分类模型项目实战
  • 前端工程化之前端工程化详解 包管理工具
  • Haskell语言的二进制与编码
  • 基于隐私计算的数据共享与分析平台V1.0源代码说明文档
  • AtCoder AT_abc397_d [ABC397D] Cubes
  • leetcode hot100普通动态规划/基础DP