分类讨论 + 顺序遍历，固定列表 / 哈希映射 + 滑动窗口，3 解法求解《904. 水果成篮》
例题
904. 水果成篮
你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 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
答案
分类讨论 + 顺序遍历
分别记录 两个数字 的的起始和终止位置，顺序遍历，分类讨论
var totalFruit = function(fruits) {
const n = fruits.length
let a = b = aStart = aEnd = bStart = bEnd = r = -1
for (let i = 0; i < n; i++) {
if (a === fruits[i]) {
aEnd = i
} else if (b === fruits[i]) {
bEnd = i
} else if (a === -1) {
a = fruits[i]
aStart = aEnd = i
} else if (b === -1) {
b = fruits[i]
bStart = bEnd = i
} else {
if (fruits[i - 1] === a) {
aStart = Math.max(aStart, bEnd + 1)
} else {
a = b
aStart = Math.max(aEnd + 1, bStart)
aEnd = bEnd
}
b = fruits[i]
bStart = bEnd = i
}
r = Math.max(r, Math.max(aEnd, bEnd) - aStart + 1)
}
return r
};function totalFruit(fruits: number[]): number {
const n = fruits.length
let a = -1, b = -1, aStart = -1, aEnd = -1, bStart = -1, bEnd = -1, r = 0
for (let i = 0; i < n; i++) {
if (a === fruits[i]) aEnd = i
else if (b === fruits[i]) bEnd = i
else if (a === -1) {
a = fruits[i]
aStart = bEnd = i
} else if (b === -1) {
b = fruits[i]
bStart = bEnd = i
} else {
if (fruits[i - 1] === a) {
aStart = Math.max(aStart, bEnd + 1)
} else {
a = b
aStart = Math.max(aEnd + 1, bStart)
aEnd = bEnd
}
b = fruits[i]
bEnd = i
}
r = Math.max(r, Math.max(aEnd, bEnd) - aStart + 1)
}
return r
};class Solution {
function totalFruit($fruits) {
$n = count($fruits);
$a = $b = $aStart = $bStart = $aEnd = $bEnd = $r = -1;
for ($i = 0; $i < $n; $i++) {
if ($a === $fruits[$i]) $aEnd = $i;
elseif ($b === $fruits[$i]) $bEnd = $i;
elseif ($a === -1) {
$a = $fruits[$i];
$aStart = $aEnd = $i;
} elseif ($b === -1) {
$b = $fruits[$i];
$bStart = $bEnd = $i;
} else {
if ($fruits[$i - 1] === $a) {
$aStart = max($aStart, $bEnd + 1);
} else {
$aStart = max($bStart, $aEnd + 1);
$a = $b;
$aEnd = $bEnd;
}
$b = $fruits[$i];
$bStart = $bEnd = $i;
}
$r = max($r, max($aEnd, $bEnd) - $aStart + 1);
}
return $r;
}
}func totalFruit(fruits []int) int {
a, b, aStart, aEnd, bStart, bEnd, r := -1, -1, -1, -1, -1, -1, -1
for i, fruit := range fruits {
if a == fruit {
aEnd = i
} else if b == fruit {
bEnd = i
} else if a == -1 {
a = fruit
aStart = i
aEnd = i
} else if b == -1 {
b = fruit
bStart = i
bEnd = i
} else {
if fruits[i - 1] == a {
aStart = max(aStart, bEnd + 1)
} else {
aStart = max(bStart, aEnd + 1)
a = b
aEnd = bEnd
}
b = fruit
bStart = i
bEnd = i
}
r = max(r, max(aEnd, bEnd) - aStart + 1)
}
return r
}
func max(a, b int) int {
if a > b {
return a
}
return b
}class Solution {
public int totalFruit(int[] fruits) {
int n = fruits.length, a = -1, b = -1, aStart = -1, aEnd = -1, bStart = -1, bEnd = -1, r = -1;
for (int i = 0; i < n; i++) {
if (a == fruits[i]) aEnd = i;
else if (b == fruits[i]) bEnd = i;
else if (a == -1) {
a = fruits[i];
aStart = i;
aEnd = i;
} else if (b == -1) {
b = fruits[i];
bStart = i;
bEnd = i;
} else {
if (fruits[i - 1] == a) {
aStart = Math.max(aStart, bEnd + 1);
} else {
aStart = Math.max(bStart, aEnd + 1);
aEnd = bEnd;
a = b;
}
b = fruits[i];
bStart = i;
bEnd = i;
}
r = Math.max(r, Math.max(aEnd, bEnd) - aStart + 1);
}
return r;
}
}public class Solution {
public int TotalFruit(int[] fruits) {
int n = fruits.Length, a = -1, b = -1, aStart = -1, aEnd = -1, bStart = -1, bEnd = -1, r = -1;
for (int i = 0; i < n; i++) {
if (a == fruits[i]) aEnd = i;
else if (b == fruits[i]) bEnd = i;
else if (a == -1) {
a = fruits[i];
aStart = i;
aEnd = i;
} else if (b == -1) {
b = fruits[i];
bStart = i;
bEnd = i;
} else {
if (fruits[i - 1] == a) {
aStart = Math.Max(aStart, bEnd + 1);
} else {
aStart = Math.Max(bStart, aEnd + 1);
aEnd = bEnd;
a = b;
}
b = fruits[i];
bStart = i;
bEnd = i;
}
r = Math.Max(r, Math.Max(aEnd, bEnd) - aStart + 1);
}
return r;
}
}#define MAX(a, b) (a > b ? a : b)
int totalFruit(int* fruits, int fruitsSize){
int a = -1, b = -1, aStart = -1, aEnd = -1, bStart = -1, bEnd = -1, r = -1;
for (int i = 0; i < fruitsSize; i++) {
if (a == fruits[i]) aEnd = i;
else if (b == fruits[i]) bEnd = i;
else if (a == -1) {
a = fruits[i];
aStart = i;
aEnd = i;
} else if (b == -1) {
b = fruits[i];
bStart = i;
bEnd = i;
} else {
if (fruits[i - 1] == a) {
aStart = MAX(aStart, bEnd + 1);
} else {
aStart = MAX(aStart, aEnd + 1);
aEnd = bEnd;
a = b;
}
b = fruits[i];
bStart = i;
bEnd = i;
}
r = MAX(r, MAX(aEnd, bEnd) - aStart + 1);
}
return r;
}class Solution {
public:
int totalFruit(vector<int>& fruits) {
int n = fruits.size(), a = -1, b = -1, aStart = -1, aEnd = -1, bStart = -1, bEnd = -1, r = -1;
for (int i = 0; i < n; i++) {
if (a == fruits[i]) aEnd = i;
else if (b == fruits[i]) bEnd = i;
else if (a == -1) {
a = fruits[i];
aStart = i;
aEnd = i;
} else if (b == -1) {
b = fruits[i];
bStart = i;
bEnd = i;
} else {
if (fruits[i - 1] == a) {
aStart = max(aStart, bEnd + 1);
} else {
aStart = max(bStart, aEnd + 1);
a = b;
aEnd = bEnd;
}
b = fruits[i];
bStart = i;
bEnd = i;
}
r = max(r, max(aEnd, bEnd) - aStart + 1);
}
return r;
}
};class Solution:
def totalFruit(self, fruits: List[int]) -> int:
a, b, aStart, bStart, aEnd, bEnd, r = -1, -1, -1, -1, -1, -1, -1
for i, fruit in enumerate(fruits):
if a == fruit: aEnd = i
elif b == fruit: bEnd = i
elif a == -1: a, aStart, aEnd = fruit, i, i
elif b == -1: b, bStart, bEnd = fruit, i, i
else:
if a == fruits[i - 1]: aStart = max(aStart, bEnd + 1)
else: aStart, aEnd, a = max(bStart, aEnd + 1), bEnd, b
b, bStart, bEnd = fruit, i, i
r = max(r, max(aEnd, bEnd) - aStart + 1)
return r固定列表 + 滑动窗口 + 双指针
var totalFruit = function(fruits) {
const n = fruits.length, h = new Uint32Array(n)
let d = 0, r = 0
for (let left = 0, right = 0; right < n; right++) {
if (h[fruits[right]] === 0) d++
h[fruits[right]]++
while (d === 3) {
h[fruits[left]]--
if (h[fruits[left]] === 0) d--
left++
}
r = Math.max(r, right - left + 1)
}
return r
};function totalFruit(fruits: number[]): number {
const n = fruits.length, h = new Uint32Array(n)
let d = 0, r = 0
for (let left = 0, right = 0; right < n; right++) {
if (h[fruits[right]]++ === 0) d++
while (d === 3) if (--h[fruits[left++]] === 0) d--
r = Math.max(r, right - left + 1)
}
return r
};class Solution {
function totalFruit($fruits) {
$h = array_fill(0, count($fruits), 0);
$left = $d = $r = 0;
foreach ($fruits as $right => $fruit) {
if ($h[$fruit]++ === 0) $d++;
while ($d === 3) if (--$h[$fruits[$left++]] === 0) $d--;
$r = max($r, $right - $left + 1);
}
return $r;
}
}func totalFruit(fruits []int) int {
h, d, r, left := make([]int, len(fruits)), 0, 0, 0
for right, fruit := range fruits {
if h[fruit] == 0 {
d++
}
h[fruit]++
for ;d == 3; left++ {
h[fruits[left]]--
if h[fruits[left]] == 0 {
d--
}
}
r = max(r, right - left + 1)
}
return r
}
func max(a, b int) int {
if a > b {
return a
}
return b
}class Solution {
public int totalFruit(int[] fruits) {
int n = fruits.length, d = 0, r = 0;
int[] h = new int[n];
for (int left = 0, right = 0; right < n; right++) {
if (h[fruits[right]]++ == 0) d++;
while (d == 3) if (--h[fruits[left++]] == 0) d--;
r = Math.max(r, right - left + 1);
}
return r;
}
}public class Solution {
public int TotalFruit(int[] fruits) {
int n = fruits.Length, d = 0, r = 0;
int[] h = new int[n];
for (int left = 0, right = 0; right < n; right++) {
if (h[fruits[right]]++ == 0) d++;
while (d == 3) if (--h[fruits[left++]] == 0) d--;
r = Math.Max(r, right - left + 1);
}
return r;
}
}#define MAX(a, b) (a > b ? a : b)
int totalFruit(int* fruits, int fruitsSize){
int* h = malloc(sizeof(int) * fruitsSize);
memset(h, 0, sizeof(int) * fruitsSize);
int d = 0, r = 0;
for (int left = 0, right = 0; right < fruitsSize; right++) {
if (h[fruits[right]]++ == 0) d++;
while (d == 3) if (--h[fruits[left++]] == 0) d--;
r = MAX(r, right - left + 1);
}
return r;
}class Solution {
public:
int totalFruit(vector<int>& fruits) {
int n = fruits.size(), d = 0, r = 0;
vector<int> h(n, 0);
for (int left = 0, right = 0; right < n; right++) {
if (h[fruits[right]]++ == 0) d++;
while (d == 3) if (--h[fruits[left++]] == 0) d--;
r = max(r, right - left + 1);
}
return r;
}
};class Solution:
def totalFruit(self, fruits: List[int]) -> int:
n = len(fruits)
h, left, d, r = [0] * n, 0, 0, 0
for right, fruit in enumerate(fruits):
if h[fruit] == 0: d += 1
h[fruit] += 1
while d == 3:
h[fruits[left]] -= 1
if h[fruits[left]] == 0: d -= 1
left += 1
r = max(r, right - left + 1)
return r哈希映射 + 滑动窗口 + 双指针
var totalFruit = function(fruits) {
const n = fruits.length, h = new Map
let r = 0
for (let left = 0, right = 0; right < n; right++) {
h.set(fruits[right], (h.get(fruits[right]) || 0) + 1)
while (h.size === 3) {
h.set(fruits[left], (h.get(fruits[left]) || 0) - 1)
if (h.get(fruits[left]) === 0) h.delete(fruits[left])
left++
}
r = Math.max(r, right - left + 1)
}
return r
};function totalFruit(fruits: number[]): number {
const n = fruits.length, h = Object.create(null)
let r = 0
for (let left = 0, right = 0; right < n; right++) {
h[fruits[right]] = (h[fruits[right]] || 0) + 1
while (Object.keys(h).length === 3) if (--h[fruits[left++]] === 0) delete h[fruits[left - 1]]
r = Math.max(r, right - left + 1)
}
return r
};class Solution {
function totalFruit($fruits) {
$h = [];
$left = $r = 0;
foreach ($fruits as $right => $fruit) {
$h[$fruit]++;
while (count($h) === 3) if (--$h[$fruits[$left++]] === 0) unset($h[$fruits[$left - 1]]);
$r = max($r, $right - $left + 1);
}
return $r;
}
}func totalFruit(fruits []int) int {
h, r, left := map[int]int{}, 0, 0
for right, fruit := range fruits {
h[fruit]++
for len(h) == 3 {
h[fruits[left]]--
if h[fruits[left]] == 0 {
delete(h, fruits[left])
}
left += 1
}
r = max(r, right - left + 1)
}
return r
}
func max(a, b int) int {
if a > b {
return a
}
return b
}class Solution {
public int totalFruit(int[] fruits) {
int n = fruits.length, r = 0;
Map<Integer, Integer> h = new HashMap<Integer, Integer>();
for (int left = 0, right = 0; right < n; right++) {
h.put(fruits[right], h.getOrDefault(fruits[right], 0) + 1);
while (h.size() == 3) {
h.put(fruits[left], h.getOrDefault(fruits[left], 0) - 1);
if (h.get(fruits[left]) == 0) h.remove(fruits[left]);
left++;
}
r = Math.max(r, right - left + 1);
}
return r;
}
}public class Solution {
public int TotalFruit(int[] fruits) {
int n = fruits.Length, r = 0;
IDictionary<int, int> h = new Dictionary<int, int>();
for (int left = 0, right = 0; right < n; right++) {
h.TryAdd(fruits[right], 0);
h[fruits[right]]++;
while (h.Count == 3) {
h[fruits[left]]--;
if (h[fruits[left]] == 0) h.Remove(fruits[left]);
left++;
}
r = Math.Max(r, right - left + 1);
}
return r;
}
}#define MAX(a, b) (a > b ? a : b)
typedef struct {
int key;
int val;
UT_hash_handle hh;
} HashItem;
int totalFruit(int* fruits, int fruitsSize){
HashItem* h = NULL;
int r = 0;
for (int left = 0, right = 0; right < fruitsSize; right++) {
HashItem* pEntry = NULL;
HASH_FIND_INT(h, &fruits[right], pEntry);
if (pEntry == NULL) {
pEntry = malloc(sizeof(HashItem));
pEntry->key = fruits[right];
pEntry->val = 1;
HASH_ADD_INT(h, key, pEntry);
} else {
pEntry->val++;
}
while (HASH_COUNT(h) == 3) {
HASH_FIND_INT(h, &fruits[left], pEntry);
if (--pEntry->val == 0) {
HASH_DEL(h, pEntry);
free(pEntry);
}
left++;
}
r = MAX(r, right - left + 1);
}
HashItem* cur, *tmp;
HASH_ITER(hh, h, cur ,tmp) {
HASH_DEL(h, cur);
free(cur);
}
return r;
}class Solution {
public:
int totalFruit(vector<int>& fruits) {
int n = fruits.size(), d = 0, r = 0;
unordered_map<int, int> h;
for (int left = 0, right = 0; right < n; right++) {
h[fruits[right]]++;
while (h.size() == 3) if (--h[fruits[left++]] == 0) h.erase(fruits[left - 1]);
r = max(r, right - left + 1);
}
return r;
}
};class Solution:
def totalFruit(self, fruits: List[int]) -> int:
n = len(fruits)
h, left, d, r = dict(), 0, 0, 0
for right, fruit in enumerate(fruits):
h[fruit] = h.get(fruit, 0) + 1
while len(h) == 3:
h[fruits[left]] -= 1
if h[fruits[left]] == 0: h.pop(fruits[left])
left += 1
r = max(r, right - left + 1)
return rclass Solution:
def totalFruit(self, fruits: List[int]) -> int:
n = len(fruits)
h, left, d, r = Counter(), 0, 0, 0
for right, fruit in enumerate(fruits):
h[fruit] += 1
while len(h) == 3:
h[fruits[left]] -= 1
if h[fruits[left]] == 0: h.pop(fruits[left])
left += 1
r = max(r, right - left + 1)
return r