题目:
你正在探访一家农场,农场从左到右种植了一排果树。这些树用一个整数数组 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] 这两棵树。 复制代码
题目来源:水果成篮
题解:
看完题目很懵,这题这么去问多少有点毛病吧?!说 fruits[i] 是代表 i 颗树上的种类,在题解中又看到官网说:数字相同的就代表是种类相同的水果;
这样理解的话,[1,2,1] 就是 1 一类,2 一类,尽可能地包含长的子数组,但又只有两类,所以结果是 [1,2,3],长度为 3
同样的:[0,1,2,2] 就是 [1,2,2],长度为 3 ,包含了两类,1 和 2 ;
所以,其实这道题目可以理解为求只包含两种元素的最长连续子序列;
基本思路: 滑动窗口
设两个双指针 l、r,r 不断前移,只要遇到两个篮子之外的水果品种,便更新 L、篮子中的水果品种 maxLen。
例如:[0,6,6,6,1,4,4,6]
第一种水果:0,第二种水果:6,第三种水果:1。当遇到第三种水果1时,要放弃第一种水果0,这时第二种水果6要保持从索引1开始,不是3。
如果是 [0,6,0,6,1,4,4,6],遇到第三种水果 1 时要放弃第一种水果0,这时第二种水果要保持从3开始。
记录 每一次水果品种发生变化 且 是该水果品种第一次出现时的索引;
当遇到第三种水果时,n 就是上一种水果的第一次出现的起始位置,也是左指针的位置。
JavaScript 实现:
var totalFruit = function(fruits) { let l = 0; let maxLen = 0; let n = 0 let arr = [fruits[l]] for(let r = 0; r < fruits.length; r++){ if(!arr.includes(fruits[r])){ if(arr.length <= 1){ arr[1] = fruits[r] }else{ l = n arr[0] = fruits[r-1] arr[1] = fruits[r] } } if(fruits[r] !== fruits[n]){ n = r } maxLen = Math.max(maxLen,r-l+1) } return maxLen };
小结:如果面试中遇到这题不熟悉肯定很难读懂题意,转换理解为处理 包含两种元素的最长连续子序列 就好理解多了,什么水果成篮,感觉有点把实际想问的问题复杂化了。不过算法解题中,读题真的也很关键。