904.水果成篮

【LetMeFly】两种方法小详解:904.水果成篮

力扣题目链接:https://leetcode.cn/problems/fruit-into-baskets/

你正在探访一家农场,农场从左到右种植了一排果树。这些树用一个整数数组 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

方法一:先存为[<5个3>, <6个2>, …],再统计

这种方法实现起来没有方法二简单,并且其空间复杂度也比方法二高,但优势是使用了较少的STL,在力扣上提交的结果中执行时间小于方法二(方法一用时88ms击败87%,方法二用时140ms击败46%)。如果觉得方法一复杂,也可以直接跳到方法二

这种方法的核心思想是“划分”,即:将相同的水果合并到一起。

加入原始水果为[3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, ...],那么我们就将原始水果存为<3, 5>, <2, 6>

这样预处理的时间复杂度是$O(n)$,其好处是:不用再往前逐个寻找某种水果是从下标几开始的。因为我们只需要关注两种水果,所以一旦遇到了第三种水果,我们可以立刻将“上上种水果”舍弃。

之后我们就可以愉快地遍历了,记录一下第一种水果和第二种水果的种类,接着开始往后遍历,当水果种类等于第一种或者第二种时,不断往后遍历并将水果累加(比如3, 2, 3, 2, 3, ...),直到遇到了第三种水果为止,更新答案最大值,并更新“水果1”和“水果2”

  • 时间复杂度$O(n)$,其中$n$是水果个数
  • 空间复杂度$O(M)$,其中$M$是相邻不相同的水果种类数

AC代码

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
typedef pair<int, int> pii;  // <number, times> 比如<5, 3>:5出现了3次
class Solution {
public:
int totalFruit(vector<int>& fruits) {
int n = fruits.size();
// 存为[<5个3>, <6个2>, ...]
vector<pii> append;
int lastNum = fruits[0], cnt = 1;
for (int i = 1; i <= n; i++) {
if (i == n || fruits[i] != fruits[i - 1]) {
append.push_back({fruits[i - 1], cnt});
cnt = 0;
}
cnt++;
}
if (append.size() == 1)
return append[0].second;
// 开始统计
int firstTypeLoc = 0, secondTypeLoc = 1;
int cntTimes = append[0].second + append[1].second;
int ans = cntTimes;
for (int nowTypeLoc = 2; nowTypeLoc < append.size(); nowTypeLoc++) {
while (nowTypeLoc < append.size() && (append[nowTypeLoc].first == append[firstTypeLoc].first || append[nowTypeLoc].first == append[secondTypeLoc].first)) { // 第三种水果和前两种水果之一相同
cntTimes += append[nowTypeLoc++].second;
}
ans = max(ans, cntTimes);
if (nowTypeLoc == append.size()) {
break;
}
// 更新水果1和水果2
firstTypeLoc = nowTypeLoc - 1;
secondTypeLoc = nowTypeLoc;
cntTimes = append[firstTypeLoc].second + append[secondTypeLoc].second;
}
ans = max(ans, cntTimes); // 此行不可去掉
return ans;
}
};

方法二:滑动窗口,哈希表助阵

方法一的核心是“纵览全局,统筹大局”,将一个一个分散的水果化为了一堆一堆的水果,相同且连续的水果再多,都只是“一堆”

但是其代价就是需要额外的空间来存放统计的结果。

方法二中,我们使用滑动窗口,时时遍历,时时统计,不预先处理。

使用一个“左指针”left和一个“右指针”right,在[left, right]中的水果是能够两筐放得下的水果。

右指针不断右移(扩大窗口),如果水果种类数超过了三种,左指针就开始右移(缩小窗口),直到水果种类再次为2

这样,左指针和右指针最多分别从前到后遍历一次,总时间复杂度是$O(n)$

至于窗口中有哪些水果,可以用哈希表来存放。因为最多有两种合法水果,所以哈希表中最多同时出现三种键值,总空间复杂度是$O(1)$

  • 时间复杂度$O(n)$,其中$n$是水果个数
  • 空间复杂度$O(1)$,但是需要将水果个数为0的水果从哈希表中erase掉(虽是常数复杂度,但是时间开销挺大的)

AC代码

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
int totalFruit(vector<int>& fruits) {
int n = fruits.size();
unordered_map<int, int> cnt;
int left = 0, ans = 0;
for (int right = 0; right < n; right++) {
cnt[fruits[right]]++;
while (cnt.size() > 2) {
unordered_map<int, int>::iterator it = cnt.find(fruits[left]);
it->second--;
left++;
if (!it->second) {
cnt.erase(it);
}
}
ans = max(ans, right - left + 1);
}
return ans;
}
};

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
/*
* @Author: LetMeFly
* @Date: 2025-08-05 10:28:59
* @LastEditors: LetMeFly.xyz
* @LastEditTime: 2025-08-05 10:31:43
*/
#if defined(_WIN32) || defined(__APPLE__)
#include "_[1,2]toVector.h"
#endif

class Solution {
public:
int totalFruit(vector<int>& fruits) {
int ans = 0;
unordered_map<int, int> window;
for (int l = 0, r = 0; r < fruits.size(); r++) {
window[fruits[r]]++;
while (window.size() > 2) {
if (! --window[fruits[l]]) {
window.erase(fruits[l]);
}
l++;
}
ans = max(ans, r - l + 1);
}
return ans;
}
};

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
'''
Author: LetMeFly
Date: 2025-08-05 10:28:59
LastEditors: LetMeFly.xyz
LastEditTime: 2025-08-05 10:40:16
'''
from typing import List
from collections import defaultdict

class Solution:
def totalFruit(self, fruits: List[int]) -> int:
ans = l = 0
window = defaultdict(int)
for r, v in enumerate(fruits):
window[v] += 1
while len(window) > 2:
window[fruits[l]] -= 1
if not window[fruits[l]]:
del window[fruits[l]]
l += 1
ans = max(ans, r - l + 1)
return ans

Golang

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/*
* @Author: LetMeFly
* @Date: 2025-08-05 10:28:59
* @LastEditors: LetMeFly.xyz
* @LastEditTime: 2025-08-06 18:33:14
*/
package main

func totalFruit(fruits []int) (ans int) {
window := map[int]int{}
for l, r := 0, 0; r < len(fruits); r++ {
window[fruits[r]]++
for len(window) > 2 {
window[fruits[l]]--
if window[fruits[l]] == 0 {
delete(window, fruits[l])
}
l++
}
ans = max(ans, r - l + 1)
}
return
}

Java

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
/*
* @Author: LetMeFly
* @Date: 2025-08-05 10:28:59
* @LastEditors: LetMeFly.xyz
* @LastEditTime: 2025-08-06 18:49:58
*/
import java.util.Map;
import java.util.HashMap;

class Solution {
public int totalFruit(int[] fruits) {
int ans = 0;
Map<Integer, Integer> window = new HashMap<>();
for (int l = 0, r = 0; r < fruits.length; r++) {
window.merge(fruits[r], 1, Integer::sum);
while (window.size() > 2) {
window.merge(fruits[l], -1, Integer::sum);
if (window.get(fruits[l]) == 0) {
window.remove(fruits[l]);
}
l++;
}
ans = Math.max(ans, r - l + 1);
}
return ans;
}
}

Rust

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
/*
* @Author: LetMeFly
* @Date: 2025-08-05 10:28:59
* @LastEditors: LetMeFly.xyz
* @LastEditTime: 2025-08-08 10:23:47
*/
use std::collections::HashMap;

impl Solution {
pub fn total_fruit(fruits: Vec<i32>) -> i32 {
let mut ans = 0;
let mut l = 0;
let mut window = HashMap::new();
for (r, &x) in fruits.iter().enumerate() {
*window.entry(x).or_insert(0) += 1;
while window.len() > 2 {
*window.entry(fruits[l]).or_insert(0) -= 1; // 即使键一定存在也需要or_insert(一个默认值)
if window[&fruits[l]] == 0 { // 键必须是&i32
window.remove(&fruits[l]);
}
l += 1;
}
ans = ans.max(r - l + 1);
}
ans as i32
}
}

同步发文于CSDN,原创不易,转载请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/127358126


904.水果成篮
https://blog.letmefly.xyz/2022/10/17/LeetCode 0904.水果成篮/
作者
发布于
2022年10月17日
许可协议