LC904. 水果成篮

LC904. 水果成篮

题目描述

你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类 。 你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果： 你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。 你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。 一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。 给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。

示例 1： 输入：fruits = [1,2,1] 输出：3 解释：可以采摘全部 3 棵树。 示例 2： 输入：fruits = [0,1,2,2] 输出：3 解释：可以采摘 [1,2,2] 这三棵树。 如果从第一棵树开始采摘，则只能采摘 [0,1] 这两棵树。 示例 3： 输入：fruits = [1,2,3,2,2] 输出：4 解释：可以采摘 [2,3,2,2] 这四棵树。 如果从第一棵树开始采摘，则只能采摘 [1,2] 这两棵树。 示例 4： 输入：fruits = [3,3,3,1,2,1,1,2,3,3,4] 输出：5 解释：可以采摘 [1,2,1,1,2] 这五棵树。

提示： 1 <= fruits.length <= 10^(5) 0 <= fruits[i] < fruits.length

题目解析

参考代码（许老师滑窗三问三答）

Python

题目：LC904. 水果成篮

难度：中等

作者：许老师-闭着眼睛学数理化

算法：不定滑窗

代码看不懂的地方，请直接在群上提问

本质是上求【元素种类为2的滑动窗口的最大长度】

故用哈希表Counter()维护窗口中元素种类及个数

class Solution: def totalFruit(self, fruits: List[int]) -> int: ans = 0 h = collections.Counter() left = 0 for right, x in enumerate(fruits):

Q1：对于每一个右指针right所指的元素x，做什么操作？

A1：将x加入哈希表中进行计数

h[x] += 1

Q2：什么时候要令左指针left右移？在什么条件停止右移？【循环不变量】

A2：哈希表长度为3，说明滑动窗口中的元素种类多于2种

此时需要令left右移，直到哈希表的长度为2

while(len(h)==3): # while的执行条件即为【循环不变量】 left_num = fruits[left] h[left_num] -= 1 if h[left_num] == 0: del h[left_num] left += 1

Q3：什么时候进行ans的更新？

A3：cnt 的长度小于等于2时，更新 ans。

ans = max(ans, right-left+1) return ans

Java public class Solution { public int totalFruit(int[] fruits) { int ans = 0; Map<Integer, Integer> h = new HashMap<>(); // 哈希表用于存储窗口内每种水果的数量 int left = 0;

for (int right = 0; right < fruits.length; right++) { int x = fruits[right]; // 将x加入哈希表中并计数 h.put(x, h.getOrDefault(x, 0) + 1);

// 当哈希表的种类数超过2，缩小窗口 while (h.size() == 3) { // 保证窗口内只有2种水果 int leftNum = fruits[left]; h.put(leftNum, h.get(leftNum) - 1); if (h.get(leftNum) == 0) { h.remove(leftNum); } left++; } // 更新最大长度 ans = Math.max(ans, right - left + 1); } return ans; } }

C++ class Solution { public: int totalFruit(vector<int>& fruits) { int ans = 0; unordered_map<int, int> h; // 哈希表，用于记录窗口内每种水果的数量 int left = 0;

for (int right = 0; right < fruits.size(); right++) { int x = fruits[right]; // 将x加入哈希表中并计数 h[x]++;

// 当哈希表的种类数超过2时，调整左边界 while (h.size() == 3) { // 保证窗口内只有2种水果 int leftNum = fruits[left]; h[leftNum]--; if (h[leftNum] == 0) { h.erase(leftNum); } left++; } // 更新最大长度 ans = max(ans, right - left + 1); } return ans; } };