Published in
5 min readOct 8, 2023
# 前言
藉由 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)