水果成篮
难度:
标签:
题目描述
代码结果
运行时间: 74 ms, 内存: 21.8 MB
/*
* 题目思路:
* 使用Java Stream API处理滑动窗口问题。
* 通过收集所有可能的子数组长度,其中每个子数组最多包含两种不同的水果,
* 然后找出最大的子数组长度。
*/
import java.util.*;
import java.util.stream.*;
public class Solution {
public int totalFruit(int[] fruits) {
return IntStream.range(0, fruits.length)
.map(start -> {
Map<Integer, Long> count = new HashMap<>();
return IntStream.range(start, fruits.length)
.takeWhile(end -> {
count.put(fruits[end], count.getOrDefault(fruits[end], 0L) + 1);
return count.size() <= 2;
})
.count();
})
.max()
.orElse(0);
}
}
解释
方法:
题解采用滑动窗口的方法来解决问题。首先,初始化两个篮子fruit1和fruit2以及它们的起始位置slowIndex1和slowIndex2。遍历数组,确保篮子始终包含最近访问的两种水果。如果遇到第三种水果,则需要更新篮子的内容,将当前窗口的起始位置移动到前一个水果的最后出现位置,从而保持窗口内只有两种水果。整个过程中,记录下遇到的最大水果数量。如果整个数组中只有一种水果,则直接返回数组的长度。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
j
▷🦆
s
▷🦆
o
▷🦆
n
▷