水果成篮

标签: 数组 哈希表 滑动窗口

难度: Medium

你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 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 <= 105
  • 0 <= fruits[i] < fruits.length

Submission

运行时间: 74 ms

内存: 21.8 MB

class Solution:
    def totalFruit(self, fruits: List[int]) -> int:
        slowIndex1, slowIndex2 = 0, 0
        fruit1, fruit2 = fruits[0], fruits[0]
        fruitNum = 0 #当前区间的数量
        result = 0
        for i in range(len(fruits)):
            if fruits[i] != fruit1:
                fruit2 = fruits[i]
                slowIndex2 = i
                fruitNum = i + 1
                break
        if fruit1 == fruit2:
            return len(fruits)
        for fastIndex in range(slowIndex2 + 1, len(fruits)):
            if fruits[fastIndex] == fruit1:
                fruit1, fruit2 = fruit2, fruit1
                slowIndex2 = fastIndex
                fruitNum += 1
            elif fruits[fastIndex] == fruit2:
                fruitNum += 1
            else:
                if result < fruitNum:
                    result = fruitNum
                slowIndex1 = slowIndex2
                slowIndex2 = fastIndex
                fruit1, fruit2 = fruit2, fruits[slowIndex2]
                fruitNum = fastIndex - slowIndex1 + 1
        if result < fruitNum:
            result = fruitNum
        return result

Explain

题解采用滑动窗口的方法来解决问题。首先，初始化两个篮子fruit1和fruit2以及它们的起始位置slowIndex1和slowIndex2。遍历数组，确保篮子始终包含最近访问的两种水果。如果遇到第三种水果，则需要更新篮子的内容，将当前窗口的起始位置移动到前一个水果的最后出现位置，从而保持窗口内只有两种水果。整个过程中，记录下遇到的最大水果数量。如果整个数组中只有一种水果，则直接返回数组的长度。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def totalFruit(self, fruits: List[int]) -> int:
        slowIndex1, slowIndex2 = 0, 0 # 初始化两个篮子的起始索引
        fruit1, fruit2 = fruits[0], fruits[0] # 初始化两个篮子装的水果种类
        fruitNum = 0 # 当前区间的水果数量
        result = 0 # 记录最大数量
        for i in range(len(fruits)):
            if fruits[i] != fruit1:
                fruit2 = fruits[i]
                slowIndex2 = i
                fruitNum = i + 1
                break
        if fruit1 == fruit2: # 如果整个数组中只有一种水果
            return len(fruits)
        for fastIndex in range(slowIndex2 + 1, len(fruits)):
            if fruits[fastIndex] == fruit1:
                fruit1, fruit2 = fruit2, fruit1 # 交换篮子，保持fruit2是最新访问的水果
                slowIndex2 = fastIndex
                fruitNum += 1
            elif fruits[fastIndex] == fruit2:
                fruitNum += 1
            else:
                if result < fruitNum:
                    result = fruitNum # 更新最大数量
                slowIndex1 = slowIndex2 # 更新窗口的起始位置
                slowIndex2 = fastIndex
                fruit1, fruit2 = fruit2, fruits[slowIndex2] # 更新篮子内容
                fruitNum = fastIndex - slowIndex1 + 1 # 更新当前水果数量
        if result < fruitNum:
            result = fruitNum # 最后一次检查可能的最大值
        return result

Explore

The character 'j' likely refers to JSON, which is the format in which the output and explanations are structured. JSON (JavaScript Object Notation) is a lightweight data-interchange format that is easy for humans to read and write and easy for machines to parse and generate.

The character 's' could be referring to the 'Solution' class in the provided code. The Solution class contains the method 'totalFruit' which implements the algorithm to solve the problem of collecting the maximum number of fruits into two baskets.

The letter 'o' in this context might be referring to the 'output' of the algorithm. In the provided code, the output is the result of the 'totalFruit' function, which calculates the maximum number of fruits that can be collected in two baskets under the given constraints.

The letter 'n' could refer to 'n', a common variable used to represent the size of the input, such as the number of items in an array or list. In the context of the provided algorithm, 'n' would represent the length of the 'fruits' array, which is iterated over to compute the result.