Daha sıcak güne kadar bekleme

Problem

Günlük sıcaklıklar bir dizi olarak veriliyor. Her gün için, kendisinden kesin olarak daha sıcak bir güne kadar kaç gün beklemek gerektiğini hesapla. Sonrasında daha sıcak bir gün yoksa o gün için 0 yaz. Aynı sıcaklık "daha sıcak" sayılmaz.

Girdi:  [18, 16, 17, 21, 19, 19, 23, 15]
Çıktı:  [ 3,  1,  1,  3,  2,  1,  0,  0]

Girdi:  [20, 20, 20]
Çıktı:  [ 0,  0,  0]

Netleştirme soruları

• "Daha sıcak" kesin büyük mü, büyük-eşit mi? (Kesin büyük.)
• Sonrasında daha sıcak gün yoksa 0 mı, -1 mi? (0.)
• Dizi boyutu ve sıcaklık aralığı? (10⁵ gün, 30-100 arası; küçük aralık başka bir çözüme kapı açar.)
• Boş dizi gelebilir mi?

İpuçları

Yaklaşım

Brute force: Her gün için sağa doğru ilk daha sıcak günü ara. O(n²) zaman; azalan bir dizide (hiç cevap yok) her gün sona kadar tarar.

Sağdan tarama + sıcaklık aralığı: Sıcaklık aralığı küçükse (ör. 30-100), sağdan sola giderken her sıcaklığın en son görüldüğü index'i tutup her gün için t+1..100 aralığını taramak O(n × W) verir (W = aralık genişliği). Akıllıca ama aralığa bağımlı.

Optimal, monoton stack: Cevabı henüz bulunmamış günleri bir stack'te tut. Değişmez: stack'teki günlerin sıcaklıkları alttan üste doğru artmaz (her eleman altındakinden daha soğuk ya da ona eşittir). Neden? Bir gün stack'e girdiğinde, kendisinden daha soğuk olan tüm bekleyen günlerin cevabı zaten o gündür ve hepsi çıkarılmıştır; geriye sadece ondan sıcak ya da eşit olanlar kalır.

Yeni gün day geldiğinde: tepedeki gün daha soğuksa, onun cevabı bu gündür (day - colderDay); pop et ve tekrarla. Tepedeki daha sıcak ya da eşitse dur, çünkü altındakiler de en az onun kadar sıcak. Sonra day'i push et. Döngü bitince stack'te kalanların cevabı 0'dır; Java'da int[] varsayılan olarak 0 ile başladığı için ek iş gerekmez.

"Bir sonraki daha büyük eleman" (next greater element) problem ailesinin kalıbı budur ve bu sette Trapping Rain Water ile Sliding Window Maximum'da da karşına çıkar.

Java çözümü

public final class DailyTemperatures {

    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] waitDays = new int[n];                               // varsayılan 0: daha sıcak gün yok
        int[] pending = new int[n];                                // index stack'i; sıcaklıkları azalan
        int top = -1;
        for (int day = 0; day < n; day++) {
            while (top >= 0 && temperatures[pending[top]] < temperatures[day]) {
                int colderDay = pending[top--];
                waitDays[colderDay] = day - colderDay;             // beklediği daha sıcak gün bugün
            }
            pending[++top] = day;
        }
        return waitDays;
    }
}

Stack'i ArrayDeque<Integer> yerine int[] ve bir top işaretçisiyle yazdım: boxing yok, en fazla n eleman olacağı biliniyor. ArrayDeque ile yazmak da tamamen doğru ve mülakatta daha okunaklı olabilir; bu bir mikro optimizasyon.

Karmaşıklık

• Zaman: O(n) amortize. İç while iç içe döngü gibi görünse de her index stack'e bir kez girer ve en fazla bir kez çıkar; toplam pop sayısı ≤ n.
• Bellek: O(n); azalan bir dizide tüm günler stack'te bekler.

Kenar durumlar ve testler

main içinde derlenip çalıştırıldı; 3.000 rastgele girdide (0-24 gün, 30-37 arası sıcaklık; dar aralık eşitlikleri sıklaştırır) O(n²) brute force ile karşılaştırıldı.

Mülakatçı için

Monoton stack kalıbının en temiz örneği. Gözlenecek nokta, adayın neden O(n) olduğunu amortize argümanla açıklayabilmesi; iç içe while gören birçok aday O(n²) der ya da tersine nedenini bilmeden O(n) der. İkinci nokta eşitlik: < yerine <= yazmak eşit sıcaklıkları "daha sıcak" sayar.

İpucu zamanlaması: Aday brute force'tan sonra ilerleyemezse "cevabı bulunmamış günleri nerede tutarsın?" diye sor. Stack fikri geldiğinde değişmezi (azalan sıra) kendisinin söylemesini bekle; söylemezse "stack'in içi nasıl görünüyor?" diye sor. Kod bitince karmaşıklığı ve nedenini mutlaka sor.

Takip soruları:

1. Her gün için önceki daha sıcak gün? (Beklenen: soldan tarama, push etmeden önce tepeye bakmak ya da sağdan sola tarama.)
2. Dairesel dizi: son günden sonra baştan devam ediliyor. (Beklenen: diziyi iki kez gez, index'i % n ile al; LeetCode 503.)
3. Bu bir fiyat alarmı servisi: gün içinde fiyat akıyor ve her tick için "fiyat ne zaman bu seviyeyi aşacak" sonradan raporlanacak. Stream'de bu algoritma nasıl çalışır? (Beklenen: aynı monoton stack çevrimiçi çalışır; bir tick'in cevabı, onu aşan tick geldiği anda yayınlanır; stack'te bekleyenler bellek riski.)

Benzer problemler

• Next Greater Element I ve II (LeetCode 496, 503).
• Online Stock Span (LeetCode 901).
• Largest Rectangle in Histogram (LeetCode 84).
• Trapping Rain Water (LeetCode 42) (bu sette: trapping-rain-water).
• Sliding Window Maximum (LeetCode 239): monoton deque (bu sette: sliding-window-maximum).