You are visiting a farm that has a single row of fruit trees arranged from left to right. The trees are represented by an integer array fruits where fruits[i] is the type of fruit the ith tree produces.
You want to collect as much fruit as possible. However, the owner has some strict rules that you must follow:
• You only have two baskets, and each basket can only hold a single type of fruit. There is no limit on the amount of fruit each basket can hold.
• Starting from any tree of your choice, you must pick exactly one fruit from every tree (including the start tree) while moving to the right. The picked fruits must fit in one of your baskets.
• Once you reach a tree with fruit that cannot fit in your baskets, you must stop.
Given the integer array fruits, return the maximum number of fruits you can pick.
你正拜訪了一個農場,農場中有一排果樹,由左至右排列。現在使用一個整數陣列代表這些果樹,fruits[i]代表果樹的品種。
你想要盡可能收集更多的水果,然而,農場的主人有一些規則需要你遵守:
如果使用暴力直覺破解法,一樣使用兩個迴圈,外層迴圈跑整個fruits,內層迴圈計算可以採集水果數量的總合。
【Concept】改使用Sliding window解題,先定義好window size跟pointer(a.k.a sliding window的起始點),並使用hash map記錄目前已經摘採的水果種類及數量,直到找出可以採集水果數量的最大值。
(1)設定map,記錄採集的水果種類與數量,可視為題目中的籃子
(2)設定window size,就是可以採集果樹的範圍
(3)設定sliding window的起始點start,也就是開始採集第一棵果樹的起點
(4)使用for loop開始迭代,從第一棵果樹的位置開始跑,這時將for loop裡面的end作為window的結束點,
(5)回傳可採集的範圍最大值
來解題吧
var totalFruit = function(fruits) {
// Make a map for recording fruit types
let map = new Map();
// set sliding window size
let max = 0;
// set pointer
let start = 0;
// iterate the fruit trees
for (let end = 0;end < fruits.length;end++){
//if fruit type less than 2 types and not existed in Map
if (map.size < 2 && !map.has(fruits[end])){
// add to map
map.set(fruits[end], true);
// calculate window size
max = Math.max(max, (end - start + 1));
}
//fruit type already existed
else if(map.has(fruits[end])){
max = Math.max(max, (end- start + 1));
}
//map size = 2, fruit type not existed in map
else if (!map.has(fruits[end])){
map.clear();
map.set(fruits[end], true);
map.set(fruits[end - 1], true);
start = end - 1;
//examine new start real index
while(fruits[start] == fruits[start - 1]){
start--;
}
max = Math.max(max, end - start +1);
}
}
return max;
};