LeetCode 904. 水果成篮

约 5 分钟
文章信息 8 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 字节 微软 快手
标签
数组 哈希表 滑动窗口

题目描述

✅ 904. 水果成篮

image-20260928225325152

image-20260928225325154

题意分析

两个篮子各自只能装一种水果，但容量不限。选定起点后必须连续向右采摘，不能跳过中间的树，所以目标就是找到“至多包含两种值的最长连续子数组”。

只出现一种水果的区间也合法，限制的是种类数，不是水果总数，也不要求两个篮子都装满。

解法：滑动窗口统计两类水果

核心思路

[!blue]

维护窗口 [left, right]，用频次表记录窗口内每种水果的数量。右端每加入一棵树，就把对应频次加一；如果种类超过两种，窗口不合法，需要不断从左端移除水果，直到恢复为至多两种。

移除一个水果不一定会减少种类数，同类水果可能还留在窗口中。只有频次减到 0 时才删除这个键，这样表中的键数才能准确代表当前种类数。

左端不需要回退：某个更早的起点若已使窗口包含三种水果，继续加入右侧元素也不能让这三种消失，因此它对之后的右端同样无效。每轮收缩又在第一次恢复合法时停止，所以留下的是以当前 right 结尾的最长合法窗口。

所有连续区间都有一个右端。对每个右端取得最长合法窗口，并更新全局最大长度，就能得到答案。

解题步骤

  1. 初始化空频次表、左端 left = 0 和最大长度 answer = 0。
  2. 向右扫描，把 fruits[right] 加入频次表。
  3. 只要表中种类超过两种，就减少 fruits[left] 的频次；减到 0 时删除该键，然后把左端右移一位。
  4. 窗口恢复合法后，用 right - left + 1 更新最大长度。
  5. 全部右端处理完后返回 answer，而不是最后一个窗口的长度。

代码实现

class Solution {
    public int totalFruit(int[] fruits) {
        Map<Integer, Integer> count = new HashMap<>();
        int left = 0;
        int answer = 0;

        for (int right = 0; right < fruits.length; right++) {
            count.put(fruits[right], count.getOrDefault(fruits[right], 0) + 1);

            // 完整收缩到至多两种，而不是只移除一个元素。
            while (count.size() > 2) {
                count.put(fruits[left], count.get(fruits[left]) - 1);

                if (count.get(fruits[left]) == 0) {
                    // 只有最后一个副本离开，才减少种类。
                    count.remove(fruits[left]);
                }

                left++;
            }

            answer = Math.max(answer, right - left + 1);
        }

        return answer;
    }
}

func totalFruit(fruits []int) int {
    window := make(map[int]int)
    left := 0
    answer := 0

    for right, v := range fruits {
        window[v]++
        // 完整收缩到至多两种，而不是只移除一个元素。
        for len(window) > 2 {
            window[fruits[left]]--
            if window[fruits[left]] == 0 {
                // 只有最后一个副本离开，才减少种类。
                delete(window, fruits[left])
            }
            left++
        }
        if right-left+1 > answer {
            answer = right - left + 1
        }
    }

    return answer
}

复杂度分析

  • 时间复杂度：期望 $O(n)$，n 为水果数量。右端扫描一次，左端最多前进 n 次，每个元素至多加入和移出一次。
  • 空间复杂度：$O(1)$。每轮开始时至多两种水果，加入一个新元素后最多暂时有三种，因此频次表的大小有常数上限。

关键点总结

[!green]

  • 连续采摘转化为连续窗口，两个篮子转化为至多两种值。
  • 频次归零才删除种类，收缩必须持续到整个窗口合法。
  • 左端只前进不会漏解，每个右端对应的最长合法窗口都参与更新答案。

易错点总结

[!yellow]

  • 统计全局最多的两种水果：它们可能被其他水果隔开，不能拼成一次连续采摘。
  • 出现第三种水果只移除一棵树：被移除的种类可能仍有剩余，需要循环收缩。
  • 频次为 0 仍保留键：表的大小不再等于实际种类数，窗口无法正确判断是否合法。
  • 在收缩前更新答案：此时可能仍有三种水果，不能拿非法窗口更新最大值。
  • 只返回最后窗口长度：最优区间可能在更早的位置结束。

相似题目

题目 难度 关联与区别
159. 至多包含两个不同字符的最长子串 中等 把字符换成水果种类后，同样寻找最多两种值的最长连续窗口。
340. 至多包含 K 个不同字符的最长子串 中等 本题相当于允许种类数k=2，推广到任意k时维护频次与当前种类数即可。
3. 无重复字符的最长子串 中等 用滑动窗口维护字符频次和有效左边界；本题把两种水果限制转为两类元素窗口，该题每个字符最多保留一次。
1100. 长度为 K 的无重复字符子串 中等 用滑动窗口维护字符频次和有效左边界；本题把两种水果限制转为两类元素窗口，该题固定窗口长度后统计无重复窗口。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2024/85039853
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！