跳转至

904. 水果成篮

最后更新：2024-05-10-22

链接：https://leetcode.cn/problems/fruit-into-baskets/description/

题目描述

你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类 。

你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：

  • 你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
  • 你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
  • 一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。

给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。

题目示例

输入： fruits = [1,2,1]

输出： 3

解释： 可以采摘全部 3 棵树。

输入： fruits = [0,1,2,2]

输出： 3

解释： 可以采摘 [1,2,2] 这三棵树。 如果从第一棵树开始采摘，则只能采摘 [0,1] 这两棵树。

输入： fruits = [1,2,3,2,2]

输出： 4

解释： 可以采摘 [2,3,2,2] 这四棵树。 如果从第一棵树开始采摘，则只能采摘 [1,2] 这两棵树。

输入： 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\)

思路

使用滑动窗口，每次找到两类水果，当出现新的水果时，计算当前窗口长度，并重新计算窗口的左侧边界。

C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
inline int get_maxsize(int a, int b)
{
    return a > b ? a : b;
}

int totalFruit(int* tree, int treeSize)
{
    int fruits[2];
    int max_size = 0;
    int left = 0;

    fruits[0] = tree[0];
    fruits[1] = -1;
    for (int i = 0; i < treeSize; i++) {
        // 找第二种水果
        if ((tree[i] != fruits[0]) && (fruits[1] < 0)) {
            fruits[1] = tree[i];
            continue;
        }
        
        // 出现第三种水果
        if ((tree[i] != fruits[0]) && (tree[i] != fruits[1])) {
            // printf("begin: i:%d, left:%d\n",i,left);
            int cur = i - left;
            max_size = get_maxsize(cur, max_size);
            // 从当前位置往前，找到第二个与当前位置不一样的地方，记录新的left
            int pre_fruit = tree[i - 1];
            for (int j = i - 1; j >= 0; j--) {
                if (tree[j] != pre_fruit) {
                    left = j + 1;
                    break;
                }
            }
            
            // 上一个窗口，最左侧是pre_fruit
            if (fruits[0] != pre_fruit) {
                fruits[0] = fruits[1]; 
            }
            fruits[1] = tree[i];
            // printf("end: i:%d, left:%d\n",i,left);
        }
    }
    
    max_size = get_maxsize(treeSize - left, max_size);
    return max_size;
}
Go
1