# 前言

藉由 LeetCode 來磨練演算法

# 題目連結

Fruit Into Baskets - LeetCode

# 解題思路

# 暴力解

• 維護一個 $basket array，代表當前籃子裡
• 有哪些種類的水果
• 各有幾個
• 題目限制，一個籃子裡只能有 兩個種類 的水果
• 跑兩層 loop，會把每一個 item 的起始位置作為 $left，並移動 $right 往右延伸，藉此嘗試每一種可能
• 在 $basket 沒有超過兩個種類的前提下，$right — $left + 1 為當前籃子裡的水果數量，每次都可以 已知最大水果數量 來比較，更新 已知最大水果數量

solution code 如下：

<?php
class Solution {

    /**
     * @param Integer[] $fruits
     * @return Integer
     */
    function totalFruit($fruits) {
        $basketCategoryLimit = 2;
        $basket = [];
        $fruitsLen = count($fruits);
        $maxFruits = -1;

        for ($i = 0; $i < $fruitsLen; $i++) {
            $basket = [];
            $left = $i;
            $right = $i;
            while (count($basket) <= 2 && $right < $fruitsLen) {
                $curFruitsNum = $right - $left + 1;
                $maxFruits = max($maxFruits, $curFruitsNum);
                $basket[$fruits[$right]]++;
                $right++;
            }
        }

        return $maxFruits;
    }
}

# 複雜度

如果整個 $fruits array 只有兩種水果，像是 [1,2,1,2,2,2,2,1,...]，那每一個 item 的 $right 都會往右 n 個 item，最差會是 n*(n-1)

時間複雜度為 O(N²)

空間複雜度的話，共會維護以下幾個 variable

• $basketCategoryLimit，固定為 2，不隨著 n 而變動
• $basket，每個 item 都會 assign 新的 $basket，而 $basket 固定為 2 keys & 2 values，所以為 O(n)
• $fruitsLen，不隨著 n 而變動
• $maxFruits 不會隨著 n 而變動

空間複雜度為 O(N)

# two pointer

• 跑單層 loop，利用 two pointer 來維護一個 sliding window
• 當 window 裏頭都只有兩種水果時，我們計算 最大水果數量，但當 window 超過兩種水果時，我們要將 $left pointer 向右移動，並從 $basket 當中移除掉 $left 所指向的水果，直到 $basket 當中只剩下兩種水果
• $curFruitsNum 一開始的值為 0，之後會在 $left 跟 $right 有變動時維護這個 variable
• 在每一輪 $right & $left 都調整完畢之後，針對 $curFruitsNum 以及 $maxFruitsNum 來做一次比較，藉此更新 $maxFruitsNum

# solution code

<?php
class Solution {

    /**
     * @param Integer[] $fruits
     * @return Integer
     */
    function totalFruit($fruits) {
        $basket = [];
        $fruitsCategoryLimit = 2;
        $maxFruitsNum = -1;
        $totalFruitsNum = count($fruits);
        $left = 0;
        $curFruitsNum = 0;

        for ($right = 0; $right < $totalFruitsNum; $right++) {
            // 將水果的 '種類 => 數量' 放到 $basket 中，並更新當前籃子中的總水果數量
            $basket[$fruits[$right]]++;
            $curFruitsNum++;

            // 只要籃子中超過兩種水果，就依照先進先出的順序從籃子中拿掉水果，直到種類又恢復成兩種
            while (count($basket) > $fruitsCategoryLimit) {
                $basket[$fruits[$left]]--;

                if ($basket[$fruits[$left]] === 0) {
                    unset($basket[$fruits[$left]]);
                }

                $left++;
                $curFruitsNum--;
            }

            // 當次的 loop 中，$left 跟 $right 都調整完畢了，來維護 $maxFruitsNum
            $maxFruitsNum = max($maxFruitsNum, $curFruitsNum);
        }

        return $maxFruitsNum;
    }
}

# 複雜度

空間複雜度 一一來檢視有使用到的 variable

• $basket，都維持兩個種類的水果，且不會隨著 n 而變動
• $fruitsCategoryLImit，不會隨著 n 而 init new variable
• $maxFruitsNum，同上
• $totalFruitsNum，同上
• $left，同上
• $right，同上
• $curFruitsNum，同上

時間複雜度為 O(N)

時間複雜度 while loop 的部分，最差的情況，$fruits 會像是 [1,2,3,4,5,6,...]，在這樣的情況下，每一次的 loop 都會調用 while 一次

• $basket[$fruits[$right]]++，為 n 次
• $curFruitsNum++ 為 n 次
• while 裡面為 4n 次
• $maxFruitsNum 為 n 次

總數為 7n 次，所以時間複雜度為 O(N)