水果成籃問題

題目

你正在探訪一家農場，農場從左到右種植了一排果樹。這些樹用一個整數數組 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] 這五棵樹。
      

題解

思路：用滑動視窗周遊fruits，當有新種類的水果進入視窗時

如果視窗中隻有一種水果，将這種水果加入arr數組

如果有兩種水果，更新視窗的左邊界，更新arr中水果的種類

如果進來了一種新的類型的水果 更新前一種水果的位置

更新滑動視窗的最大值

複雜度：時間複雜度O(n)

//[1,1,2,2]
//[1,1,2,2,3] -> [2,2,3]
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]//将這種水果加入arr數組
            }else{//如果有兩種水果
                l = n//更新視窗的左邊界
                arr[0] = fruits[r-1]//更新arr中水果的種類
                arr[1] = fruits[r]
            }
        }
       
        if(fruits[r] !== fruits[n]){//如果進來了一種新的類型的水果 更新前一種水果的位置
            n = r
        }

        maxLen = Math.max(maxLen,r-l+1)//更新滑動視窗的最大值
    }
    return maxLen

};      

總結

function totalFruit(fruits: number[]): number {
    // 左指針
    let p = 0
    // 函數傳回的最大值
    let max = 0
    // Map 記錄水果類型（key）和最新對應的索引值（value）
    const fruitsMap: Map<number, number> = new Map()
    for (let i = 0; i < fruits.length; i++) {
        const fruit = fruits[i]
        if (fruitsMap.has(fruit)) {
            // 利用 Map 的有序性，将 Map 中已有的水果删除後再重新添加，保證最新通路的水果在 Map 的最後面
            fruitsMap.delete(fruit)
        } else {
            if (fruitsMap.size === 2) {
                // 如果通路到第三種水果類型，此時需要删除最久未通路過的水果
                // 取 Map 中第一個水果的資訊（就是最久未通路過的水果）
                const iterator = fruitsMap.entries()
                const [firstFruit, firstFruitIndex] = iterator.next().value
                // 此時左指針應該指向 Map 中 第一個水果類型的索引加 1（也就是第二個水果類型的起始位置）
                p = firstFruitIndex + 1
                // 删除 Map 中第一個水果
                fruitsMap.delete(firstFruit)
            }
        }
        fruitsMap.set(fruit, i)
        max = Math.max(i - p + 1, max)
    }
    return max
}