news 2026/4/18 3:35:03

双指针专题(六):贪婪的采摘者——「水果成篮」

作者头像

张小明

前端开发工程师

1.2k 24
文章封面图
双指针专题(六):贪婪的采摘者——「水果成篮」

场景翻译:

  • 题目说:你有两个篮子,每个篮子只能装一种水果。你从任意一棵树开始往右走,每棵树摘一个,一旦遇到第三种水果,你就不能摘了(因为篮子装不下了),采摘结束。

  • 人话翻译:给定一个数组fruits,请你找到最长的连续子数组,使得这个子数组中至多包含 2 种不同的元素

例子:fruits = [1, 2, 3, 2, 2]

  1. [1, 2]:有 1 和 2 两种。长度 2。

  2. 遇到 3:变成[1, 2, 3](三种了),不行。

    • 必须扔掉前面的 1,窗口变成[2, 3]

  3. 遇到 2:[2, 3, 2](还是 2 和 3 两种),可以!长度 3。

  4. 遇到 2:[2, 3, 2, 2](还是 2 和 3 两种),可以!长度 4

最终答案:4。

力扣 904. 水果成篮

https://leetcode.cn/problems/fruit-into-baskets/

题目分析:

  • 输入:整数数组fruits

  • 目标:找到包含不超过 2 种元素的最长子数组长度。

  • 输出:最大长度。

核心思维:Map 计数器 + 滑动窗口

我们需要一个哈希表 (Map)来充当“篮子”的角色。

  • Key:水果的种类 ID。

  • Value:该种类在当前窗口内的数量

操作逻辑:

  1. 进窗口 (right):把水果加入 Map,计数 +1。

  2. 检查篮子 (Map.size)

    • 如果Map.size > 2,说明窗口里有 3 种水果了,超载了!

    • 出窗口 (left)

      • 开始收缩左边界,把fruits[left]从 Map 里减 1。

      • 关键点:如果减完之后,某个水果的数量变成了0,必须把它从 Map 里delete掉!

      • 只有当Map.size重新回到 2(或更少)时,while循环才能停止。

  3. 更新答案:每次窗口合法时,更新maxLen

代码实现 (JavaScript)

JavaScript

/** * @param {number[]} fruits * @return {number} */ var totalFruit = function(fruits) { let left = 0; let maxLen = 0; // 篮子:记录当前窗口中,每种水果的数量 // key: 水果ID, value: 数量 const basket = new Map(); for (let right = 0; right < fruits.length; right++) { // 1. 进窗口:把右边的水果放进篮子 const rightFruit = fruits[right]; basket.set(rightFruit, (basket.get(rightFruit) || 0) + 1); // 2. 检查:如果篮子里的种类超过 2 种,必须收缩左边界 while (basket.size > 2) { const leftFruit = fruits[left]; // 把左边的水果拿出去 basket.set(leftFruit, basket.get(leftFruit) - 1); // 核心细节:如果这种水果的数量减为 0 了,必须彻底从 Map 中删除 // 否则 Map.size 还是 3,循环不会停,逻辑就错了 if (basket.get(leftFruit) === 0) { basket.delete(leftFruit); } // 左指针前移 left++; } // 3. 此时篮子里一定 <= 2 种,更新最大长度 maxLen = Math.max(maxLen, right - left + 1); } return maxLen; };

深度辨析:为什么必须delete

假设窗口是[1, 2, 3],Map 是{1:1, 2:1, 3:1}(Size=3)。 如果不delete

  • left移出 1。Map 变成{1:0, 2:1, 3:1}

  • Map.size 依然是 3!(因为 key1还在,只是值为 0)。

  • while循环会继续执行,继续移出 2... 直到把篮子空到只剩两种 Key 为止。

  • 这会导致窗口缩得过小,甚至逻辑死循环。

  • 所以,“数量归零 = 彻底移除”是这道题的逻辑核心。

总结

这道题是“至多包含 K 个不同字符的最长子串”问题的标准模板(本题 K=2)。 如果你以后遇到求“至多 K 个”的题目,直接把代码里的basket.size > 2改成basket.size > K即可直接秒杀。


下一题预告:最小覆盖子串

好了,简单的滑动窗口结束了。我们要迎来双指针专题的终极 BOSS——LC 76. 最小覆盖子串(Hard)。

  • 之前的题都是窗口**“太胖了”**(超标了)才收缩。

  • 这道题正好相反:窗口**“太瘦了”(还没凑齐目标字符)就要扩张,一旦“吃饱了”(凑齐了)就要开始拼命收缩**,试图找到一个最短的、能满足要求的窗口。

这就好比:你要去超市买齐清单上的[A, B, C]三样东西。

  • 你一直往前走,直到购物车里凑齐了这三样(可能还有多余的 D, E)。

  • 然后你尝试从购物车底部拿走一些东西,看看能不能在保持 A, B, C 依然齐全的情况下,让付钱的东西最少。

准备好挑战这道 Hard 题了吗?这将是你滑动窗口的毕业考试

版权声明: 本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若内容造成侵权/违法违规/事实不符,请联系邮箱:809451989@qq.com进行投诉反馈,一经查实,立即删除!
网站建设 2026/4/13 17:42:17

为什么顶级公司都在用Uvicorn部署FastAPI?背后的技术逻辑首次公开

第一章&#xff1a;为什么顶级公司都在用Uvicorn部署FastAPI&#xff1f;在构建高性能、可扩展的现代Web API时&#xff0c;FastAPI凭借其类型提示、自动文档生成和出色的性能脱颖而出。然而&#xff0c;真正让FastAPI在生产环境中大放异彩的&#xff0c;是其与Uvicorn的深度集…

作者头像 李华
网站建设 2026/4/17 18:05:10

PyCharm激活码永久免费?不!但VoxCPM-1.5-TTS可合法免费使用

VoxCPM-1.5-TTS&#xff1a;如何用合法、免费的方式实现高质量语音合成&#xff1f; 在智能客服自动播报、有声书批量生成、视障人士辅助阅读等场景中&#xff0c;文本转语音&#xff08;Text-to-Speech, TTS&#xff09;技术正变得无处不在。但你是否也曾为高昂的商用API费用…

作者头像 李华
网站建设 2026/4/8 1:58:35

抑郁症心理疏导:深夜倾诉时有人温柔回应

抑郁症心理疏导&#xff1a;深夜倾诉时有人温柔回应 深夜两点&#xff0c;手机屏幕亮起。一个人蜷在床角&#xff0c;指尖颤抖地敲下&#xff1a;“我好累&#xff0c;没人懂我。” 没有等待客服响应的转接音&#xff0c;也没有冰冷的自动回复。几秒后&#xff0c;一个温和的声…

作者头像 李华
网站建设 2026/4/4 17:42:40

智能硬件集成:VoxCPM-1.5-TTS在IoT设备上的轻量化部署

智能硬件集成&#xff1a;VoxCPM-1.5-TTS在IoT设备上的轻量化部署 在智能家居、儿童教育机器人和无障碍辅助设备日益普及的今天&#xff0c;用户对语音交互体验的要求早已超越“能说话”这一基础功能。人们期待的是自然流畅、富有情感、甚至能模仿亲人声音的个性化语音输出。然…

作者头像 李华