Buying Fruits Problem in Java

问题描述

想象一下，你在排成一排的连成一片的果树上采摘水果。每棵树都结有一种特定的水果。你有两个篮子，每个篮子都可以无限容量地装一种水果。你从任意一棵果树开始采摘，然后走向右边的下一棵果树。

你一次只能用两个篮子装两种不同的水果。因此，你的目标是尽可能多地收集水果。一旦遇到第三种水果，而它无法放入你现有的任何一个篮子时，你必须停止采摘。

这个问题就是要找出在遵循这些规则的前提下，你最多能收集多少水果。

你将得到一个名为 fruits 的数组，其中 fruits 中的每个元素代表第 i 棵树 [i] 结出的水果类型。你需要根据所述规则，计算出你最多可以收集多少水果。

解决问题的方法

这个问题是滑动窗口策略的一个变体，这是一种用于控制更大数据集一部分的有用方法。在这种情况下，最长的树链就是我们可以从中收集水果，足以装满两个篮子的子集。

为了解决这个问题，我们会维护一个在各种果树集合上滑动的“窗口”。

这个窗口应该包含最多包含两种不同水果品种的最长连续的树的序列。我们将使用一个哈希映射，在将窗口从数组的开头滑动到结尾的过程中，计算窗口中每种水果的数量。

如果引入新的水果品种导致窗口包含超过两种品种，我们将从左侧缩小窗口，直到它再次只包含两种品种的水果。

解决此问题的步骤如下：

初始化一个空的 哈希映射，用于跟踪当前窗口中每种水果的数量。

1. 使用两个 指针 来表示滑动窗口的开始和结束。两个指针最初都指向 数组 的开头。
2. 使用结束指针遍历数组，以扩展窗口以包含更多的水果。
3. 假设添加一种水果导致窗口包含超过两种品种。将开始指针向前移动，以缩小窗口，直到它再次只包含最多两种品种的水果。
4. 在此过程中，跟踪窗口的最大大小。
5. 最大窗口的长度将代表你可以收集的水果数量。

这种方法确保每个水果只被添加和移除一次，从而实现 O(n) 的时间复杂度，其中 n 是树的数量。

输入

1. 初始化：fruitCount = {}, start = 0, maxFruits = 0。
2. 迭代
   
   • end = 0：添加水果类型 1 -> fruitCount = {1: 1}。
   • end = 1：添加水果类型 2 -> fruitCount = {1: 1, 2: 1}。
   • end = 2：添加水果类型 1 -> fruitCount = {1: 2, 2: 1}。
   • end = 3：添加水果类型 2 -> fruitCount = {1: 2, 2: 2}。
     现在，我们的窗口中只有 2 种水果：[1, 2, 1, 2]。
   • end = 4：添加水果类型 3 -> fruitCount = {1: 2, 2: 2, 3: 1}。
   
   此时，我们有超过 2 种水果。我们需要从左侧缩小窗口。
   
   • 缩小
     
     • start = 0：移除水果类型 1 -> fruitCount = {1: 1, 2: 2, 3: 1}。
     • start = 1：移除水果类型 2 -> fruitCount = {1: 1, 2: 1, 3: 1}。
     • start = 2：移除水果类型 1 -> fruitCount = {2: 1, 3: 1}。
   
   窗口再次恰好有 2 种水果，其长度为 3（end - start + 1 = 4 - 2 + 1 = 3）。
3. 继续此过程，直到到达数组末尾。
   我们可以找到的最长窗口（最多包含两种水果）是 [1, 2, 1, 2]，其长度为 4。

输出

 
4   

让我们在 Java 程序中实现上述方法。

文件名：FruitsBasket.java

输出

 
Maximum number of fruits collected: 3
Maximum number of fruits collected: 3
Maximum number of fruits collected: 4
Maximum number of fruits collected: 5   

复杂度分析

时间复杂度

在上述方法中，每个元素最多被处理两次（一次用于添加，一次用于可能的移除），时间复杂度为 O(n)。

空间复杂度

O(1)（基本恒定，因为滑动窗口只需要监控两种水果，因此哈希映射的大小最多为三个）。