（C语言）力扣 904.水果成篮

写在所有的前面：

本文采用C语言实现代码

题目说明

题目：力扣 904.水果成篮

题目出处

力扣 904.水果成篮
https://leetcode.cn/problems/fruit-into-baskets/

题目描述Description

你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果种类 。
你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：

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

输入Input

一个整数数组 fruits
一个整数 水果数量fruitsSize

输出Output

你可以收集的水果的最大数目。

样例Sample

输入1

fruits = [1,2,1]

输出1

3

解释1

可以采摘全部 3 棵树

输入2

fruits = [0,1,2,2]

输出2

3

解释2

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

更多样例见连接

限制Hint

1 <= fruits.length <= 105
0 <= fruits[i] < fruits.length

C语言的代码接口为

int totalFruit(int* fruits, int fruitsSize) {
    
}

自测用主函数部分

int main()
{
	int fruits[] = { 1,2,1 };
	printf("%d", totalFruit(fruits, 3));
}

解答说明

方案

解题思路

a 果实，b 果实
nextnum 最近的相同果实数量
allnum 最近的 a b 果实数量
maxnum 最大量

一般情况

1. 当前水果可摘 if (fruits[i] == a || fruits[i] == b)
   1. 最近的 a b 果实数量allnum +1
   2. 水果相同则最近的相同果实数量nextnum +1
   3. 水果改变则最近的相同果实数量nextnum重置为 1
2. 当前水果是全新的果实
   1. 通过最近的两水果数量allnum更新最大数量maxnum（保留更大的）
   2. 通过最近的相同果实数量nextnum +1更新最近的两水果数量allnum
   3. 水果改变，最近的相同果实数量nextnum重置为 1
   4. 更新水果种类（保留较近的水果）

特殊情况

遍历所有水果后再更新一次最大数量maxnum
第一颗水果必定更新水果种类if (i == 0)

代码实现

int totalFruit(int* fruits, int fruitsSize)
{
	int i = 0;//第i颗果树
	int a = -1, b = -1, nextnum = 0, allnum = 0, maxnum = 0;//a果实，b果实，最近的相同果实数量，最近的ab果实数量，最大量
	//从前向后遍历
	while (i < fruitsSize)
	{
		//如果水果符合
		if (fruits[i] == a || fruits[i] == b)
		{
			allnum++;
			//如果水果相同
			if (i > 0 && fruits[i] == fruits[i - 1])
				nextnum++;
			//如果水果改变
			else
				nextnum = 1;
		}
		else //全新的果实
		{
			//更新最大数量
			if (allnum > maxnum)
				maxnum = allnum;
			//更新最近的ab果实数量
			allnum = nextnum + 1;
			//更新最近相同果实数量
			nextnum = 1;

			//更新果实种类
			if (i == 0 || fruits[i - 1] == b)
				a = fruits[i];
			else if (fruits[i - 1] == a)
				b = fruits[i];
		}
		//下一颗果树
		i++;
	}
	//更新最大数量
	if (allnum > maxnum)
		maxnum = allnum;
	return maxnum;
}

其他解释

可能有更优解，但是懒得看了