Leetcode 84 水果成篮 | 删除子数组的最大得分-平芜编程栈

1 题目

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

2 代码实现

class Solution { public: int totalFruit(vector<int>& fruits) { unordered_map<int, int> window ; int left = 0 ; int right = 0; int n = fruits.size(); int res = 0 ; while(right < n ){ int a = fruits[right]; right++; window[a]++; while(window.size() > 2){ int b = fruits[left]; left++; window[b]--; if(window[b] == 0){ window.erase(b); } } res = max(res , right - left); } return res; } };

两段代码中left和right的更新位置不同，但结果却都正确。

class Solution { public: int totalFruit(vector<int>& fruits) { unordered_map<int, int> window ; int left = 0 ; int right = 0; int n = fruits.size(); int res = 0 ; while(right < n ){ int a = fruits[right]; window[a]++; while(window.size() > 2){ int b = fruits[left]; window[b]--; left++; if(window[b] == 0){ window.erase(b); } } right++; res = max(res , right - left); } return res; } };

这两种写法只是调整了 “元素入窗” 和 “指针移动” 的先后顺序，最终维护的滑动窗口的有效范围是完全一致的，因此计算出的窗口长度也会相同。

思考

一点思路都没有，这个和滑动窗口有什么关系？

问题与滑动窗口的关联分析

首先，我们把问题转化一下：

两个篮子对应最多两种水果类型。
必须从左到右连续采摘对应数组的连续子数组。
要收集最多水果对应找最长的符合条件的子数组。

fruits[i]中的每个数字确实只是水果类别的标识，不同的数字代表不同种类的水果，相同的数字代表同一种类的水果！

这是典型的滑动窗口（双指针）问题，属于“最长子数组最多包含 k 种元素” 的特例（这里 k=2）。

滑动窗口的核心是用左右指针维护一个窗口，保证窗口内的元素满足 “最多两种类型”。

同时不断扩大右指针，当窗口内元素超过两种时，移动左指针收缩窗口，过程中记录窗口的最大长度。

我想大概这么实现：

条件是最多包含2个元素，然后根据条件约束好滑动窗口的边界。

怎么实现最多包含2个元素？

可以用 unordered_map 来记录当前窗口内每种水果类别（数字）的数量，类别数量就是这个map对应的size()。

错误百出的代码

class Solution { public: int totalFruit(vector<int>& fruits) { unordered_map<int, int> window ; int left = 0 ; int right = 0; int n = fruits.size(); int res = 0 ; while(right < n ){ int a = fruits[right]; right++; window[a]++; while(window.size() > 2){ int b = fruits[left]; left++; window[b]--; } res = max(res , right - left); } return res; } };

错误分析

举个例子，比如输入fruits = [1,2,3,2,2]：

当right遍历到索引 2（水果 3）时，window中是{1:1, 2:1, 3:1}，window.size()=3，进入内层循环。
左指针left指向索引 0（水果 1），执行window[1]--后，window[1]变为 0，但没有删除键 1，此时window.size()仍然是 3。
内层循环会继续执行，left继续右移到索引 1（水果 2），执行window[2]--，window[2]变为 0，还是没删除键 2，window.size()依旧是 3。
这会导致左指针被过度移动，最终计算的窗口长度会偏小，得到错误的结果。

3 题目

1695. 删除子数组的最大得分

给你一个正整数数组nums，请你从中删除一个含有若干不同元素的子数组。删除子数组的得分就是子数组各元素之和。

返回只删除一个子数组可获得的最大得分。

如果数组b是数组a的一个连续子序列，即如果它等于a[l],a[l+1],...,a[r]，那么它就是a的一个子数组。

示例 1：

输入：nums = [4,2,4,5,6]输出：17解释：最优子数组是 [2,4,5,6]

示例 2：

输入：nums = [5,2,1,2,5,2,1,2,5]输出：8解释：最优子数组是 [5,2,1] 或 [1,2,5]

提示：

1 <= nums.length <= 105
1 <= nums[i] <= 104

4 代码实现

class Solution { public: int maximumUniqueSubarray(vector<int>& nums) { unordered_map<int,int> window ; int left = 0 ; int right = 0 ; int curSum = 0; int sum = 0 ; while(right < nums.size()){ int a = nums[right]; curSum+=nums[right]; right++; window[a]++; while(window[a] > 1){ int b = nums[left]; curSum -= nums[left]; left++; window[b]--; } sum = max(sum ,curSum); } return sum ; } };

思考

啥玩意，就是找一个子数组。要求连续，没有相同的元素。

子数组的和最大，最后返回一下这个子数组相加的和。

哈哈，看着高级的描述其实就是一个不定长的滑动窗口罢了。

我的思路：

1.连续

这就是滑动窗口嘛。

2.没有重复的元素

每一个进入窗口的元素都用unordered_map记录<int ,int >存放元素和出现次数，如果对应的value > 1 ，处理窗口。

3.子数组的和最大

定义一个sum，每次处理窗口发生滑动的时候更新sum的值，并且用max更新，保持这个值最大。

又写错了

class Solution { public: int maximumUniqueSubarray(vector<int>& nums) { unordered_map<int,int> window ; int left = 0 ; int right = 0 ; int sum = 0 ; while(right < nums.size()){ int curSum = 0; int a = nums[right]; right++; window[a]++; curSum+=nums[right]; while(window[a] > 1){ int b = nums[left]; left++; window[b]--; curSum -= nums[left]; } sum = max(sum ,curSum); } return sum ; } };

代码中的关键错误

curSum的初始化位置错误：你把curSum放在while循环内部，每次循环都会重置为 0，导致无法累加窗口内的元素和。
访问数组越界：right++后直接执行curSum += nums[right]，当right到达数组末尾时，nums[right]会访问到数组外的元素，触发越界错误。
求和与减和的逻辑错误：
- 累加时应该加当前的a（即nums[right-1]），而不是nums[right]。
- 收缩窗口时，应该减当前的b（即nums[left-1]），而不是nums[left]，且减和操作应该和left移动对应。
收缩窗口的条件错误：while(window[a] > 1)只判断当前元素a的重复情况，但窗口内可能存在其他元素重复的情况（比如窗口内有[1,2,1,3]，此时3不重复，但1重复，你的条件无法检测到），正确的条件应该是检查当前元素的计数是否大于 1（或用哈希集合判断是否存在）。