Mediumsliding-window
Fruit Into Baskets
Problem (yeniden ifade)
Meyveler bir sırada yetişir; her ağacın bir türü var. Bitişik bir alt dizide en fazla iki türden toplayabilirsin. Toplayabileceğin maksimum meyve sayısını döndür.
Sezgi
En fazla 2 farklı değerli en uzun alt dizi. klasik kısıtlı pencere.
Yaklaşımlar
En fazla iki tür penceresi
DoğrulanmadıZaman O(n)Alan O(1)
Fikir. Sağı genişletip türleri map’e ekle. Map’te >2 anahtar varken soldan düş. Maks pencere uzunluğunu izle.
Yürüyüş. [1,2,1,2,3] → [1,2,1,2] pencereleri uzunluk 4, sonra [2,3] uzunluk 2 → cevap 4.
Trade-off. Map boyutu geçici olarak ≤ 3; sayaçlı two pointers ile eşdeğer.
Çözüm
export function totalFruit(fruits: number[]): number {
const map = new Map<number, number>();
let left = 0, best = 0;
for (let right = 0; right < fruits.length; right++) {
const x = fruits[right]!;
map.set(x, (map.get(x) ?? 0) + 1);
while (map.size > 2) {
const y = fruits[left]!;
const c = map.get(y)! - 1;
if (c === 0) map.delete(y);
else map.set(y, c);
left++;
}
best = Math.max(best, right - left + 1);
}
return best;
}
export function totalFruit(fruits: number[]): number {
const map = new Map<number, number>();
let left = 0, best = 0;
for (let right = 0; right < fruits.length; right++) {
const x = fruits[right]!;
map.set(x, (map.get(x) ?? 0) + 1);
while (map.size > 2) {
const y = fruits[left]!;
const c = map.get(y)! - 1;
if (c === 0) map.delete(y);
else map.set(y, c);
left++;
}
best = Math.max(best, right - left + 1);
}
return best;
}
Şablon bağlantısı
En fazla iki farklı değerli sliding window (≤ 2 tür, en uzun alt dizi).
Yansıma
- “En fazla iki tür, bitişik” → en fazla 2 anahtarlı kayan pencere. Basket=2’yi k=2 karakter yerine koyabilir misin?
- Üçüncü tür gelince solu hangi kurala göre kaydırırsın?
- Tüm ağaçlar aynı tür: cevap n.