水果成篮--LeetCode

题目

你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 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. 初始化变量：获取数组长度，创建一个数组 window 用于记录每种水果的出现次数，初始化左右指针 l 和 r 为 0，结果变量 ans 为 0，篮子种类数量变量 basket 为 0。
2. 滑动窗口：使用右指针 r 不断向右扩展窗口，将新的水果加入窗口，并更新 window 数组和 basket 变量。
3. 调整窗口：当 basket 大于 2 时，使用左指针 l 缩小窗口，将窗口左侧的水果移除，直到 basket 不大于 2。
4. 更新结果：每次调整窗口后，更新 ans 为当前窗口长度 r - l 和 ans 中的较大值。
5. 返回结果：循环结束后，返回 ans。

class Solution {public int totalFruit(int[] fruits) {int n = fruits.length;// 创建一个长度为 n + 1 的整数数组 window，用于记录每种水果在当前窗口中出现的次数int[] window = new int[n + 1];// 初始化结果变量 ans 为 0，用于记录最多能采摘的水果数量// 初始化篮子种类数量变量 basket 为 0，用于记录当前窗口中水果的种类数int l = 0, r = 0, ans = 0, basket = 0;// 当右指针 r 小于数组长度 n 时，继续循环while(r < n){// 先将右指针 r 指向的水果种类在 window 数组中的计数加 1，然后右移右指针 r// 如果加 1 之前该水果种类的计数为 0，说明这是一种新的水果种类，将篮子种类数量 basket 加 1if(window[fruits[r++]]++ == 0)basket++;// 当篮子中水果的种类数大于 2 时，需要缩小窗口，以保证篮子中最多只有两种水果while(basket > 2){// 先将左指针 l 指向的水果种类在 window 数组中的计数减 1，然后右移左指针 l// 如果减 1 之后该水果种类的计数为 0，说明这种水果已经不在当前窗口中了，将篮子种类数量 basket 减 1if(window[fruits[l++]]-- == 1)basket--;}// 更新最多能采摘的水果数量，取当前窗口的长度 r - l 和之前记录的 ans 中的较大值ans = Math.max(r-l,ans);}// 返回最多能采摘的水果数量return ans;}
}

class Solution {public int totalFruit(int[] fruits) {int n = fruits.length;Map<Integer, Integer> cnt = new HashMap<Integer, Integer>();int left = 0, ans = 0;for (int right = 0; right < n; ++right) {cnt.put(fruits[right], cnt.getOrDefault(fruits[right], 0) + 1);while (cnt.size() > 2) {cnt.put(fruits[left], cnt.get(fruits[left]) - 1);if (cnt.get(fruits[left]) == 0) {cnt.remove(fruits[left]);}++left;}ans = Math.max(ans, right - left + 1);}return ans;}
}