Yağmur suyu biriktirme

Problem

Genişliği 1 olan yan yana sütunların yükseklikleri veriliyor (negatif olmayan tamsayılar). Üzerine yağmur yağdıktan sonra sütunların arasındaki çukurlarda toplam kaç birim su birikir? Su, iki yanında kendisinden yüksek bir sütun olan yerlerde birikir; dizinin iki ucundan dışarı akar.

Girdi:  [3, 0, 1, 4, 0, 2, 0, 3]
Çıktı:  12
        index:  1  2  3  4  5  6
        su:     3  2  0  3  1  3

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

Netleştirme soruları

• Dizinin iki ucu açık mı, yani su kenarlardan akıyor mu? (Evet.)
• Yükseklikler negatif olabilir mi? (Hayır.)
• Toplam int'e sığar mı? (n ≤ 2×10⁴, h ≤ 10⁵ ise en fazla 2×10⁹; sınırda. Daha büyük girdide long.)
• Tek bir sayı mı, yoksa sütun başına dağılım mı isteniyor?

İpuçları

Yaklaşım

Brute force: Her sütun için solundaki ve sağındaki maksimumu ayrı ayrı tara, min(solMax, sağMax) - h[i] ekle. O(n²) zaman, O(1) bellek.

Önek maksimumları: leftMax[i] ve rightMax[i] dizilerini iki geçişte önceden hesapla; üçüncü geçişte topla. O(n) zaman, O(n) bellek. Mülakatta bu çözüm tamamen kabul edilebilir ve genellikle önce bu beklenir.

Optimal, iki işaretçi (O(1) bellek): Formülde min olduğu için bir sütunun suyunu belirlemek üzere iki maksimumu da tam bilmemize gerek yok; küçük olanı kesin bilmek yeterli. left ve right işaretçileriyle iki uçtan başla, leftMax ve rightMax'ı yol boyunca güncelle:

• h[left] < h[right] ise: left'in sağında en az h[right] yüksekliğinde bir sütun var, dolayısıyla sağMax[left] ≥ h[right]. Öte yandan bir işaretçi yalnızca diğerinden kısa (ya da eşit) bir sütunun üzerindeyken hareket eder; bu yüzden şimdiye kadar geçilen en yüksek sütun hiçbir zaman iki işaretçinin altındaki sütunlardan yüksek değildir. Buradan leftMax ≤ h[right] ≤ sağMax[left] çıkar, yani min(solMax, sağMax) = leftMax. Sol sütunun suyu leftMax - h[left]; left++.
• Aksi halde simetrik olarak sağ tarafı işle.

Kodda leftMax'ı h[left] ile güncelleyip sonra farkı eklemek, "sütun kendisi maksimumsa su 0" durumunu ayrı bir if olmadan halleder.

Alternatif, monoton stack: Azalan yükseklikte index'leri stack'te tut; daha yüksek bir sütun geldiğinde çukurun tabanını çıkarıp suyu yatay katmanlar halinde hesapla. O(n) zaman, O(n) bellek. Hem farklı bir düşünme biçimi hem de Largest Rectangle in Histogram için hazırlık; takip sorusu olarak değerlidir.

Java çözümü

public final class TrappingRainWater {

    public int trap(int[] heights) {
        int left = 0, right = heights.length - 1;
        int leftMax = 0, rightMax = 0;
        int water = 0;
        while (left < right) {
            if (heights[left] < heights[right]) {
                // Sağda en az heights[right] kadar yüksek bir duvar var; sol sütunu leftMax belirler
                leftMax = Math.max(leftMax, heights[left]);
                water += leftMax - heights[left];
                left++;
            } else {
                rightMax = Math.max(rightMax, heights[right]);
                water += rightMax - heights[right];
                right--;
            }
        }
        return water;
    }
}

Karmaşıklık

• Zaman: O(n); her iterasyonda bir işaretçi bir adım ilerler.
• Bellek: O(1).
• Önek maksimumu versiyonu O(n) zaman, O(n) bellek; monoton stack versiyonu O(n) zaman, en kötü O(n) bellek.

Kenar durumlar ve testler

main içinde derlenip çalıştırıldı; 3.000 rastgele girdide (0-19 uzunluk, yükseklik 0-7) her sütun için sol/sağ maksimumu ayrı tarayan O(n²) brute force ile karşılaştırıldı.

Mülakatçı için

Klasik bir "Zor" soru; ama adaylar arasında ayrım çoğunlukla optimal kodda değil, tek sütun formülünü (min(solMax, sağMax) - h) bulup bulamamakta olur. Formülü bulan aday önek maksimumlarıyla O(n) çözüme kolayca geçer. İki işaretçi optimizasyonu ise "neden sadece küçük olanı bilmek yeterli?" argümanını gerektirir; bunu açıklayabilen aday güçlü bir sinyal verir.

İpucu zamanlaması: Aday çukurları "bölge bölge" simüle etmeye çalışıp karmaşık bir koda giriyorsa erken (5. dakika civarı) ilk ipucunu ver: "tek bir sütuna odaklan". Önek maksimumlu çözüm geldiyse bunun yeterli olduğunu söyle; zaman kalırsa O(1) bellek iste. İki işaretçide h[left] < h[right] koşulunun neden yeterli olduğunu açıklayamazsa ezber olabilir.

Takip soruları:

1. Monoton stack ile çöz; su nasıl yatay katmanlar halinde hesaplanır? (Beklenen: taban çıkarılır, genişlik i - stack.peek() - 1, yükseklik min(h[i], h[peek]) - h[taban].)
2. 2D versiyonu: bir yükseklik haritasında su? (Beklenen: Trapping Rain Water II, LeetCode 407; kenarlardan başlayan min-heap ile Dijkstra benzeri taşma.)
3. Sütun başına su dağılımını da döndürmek istersem çözüm değişir mi? (Beklenen: hayır, aynı döngüde dizi doldurulur; bellek O(n) olur.)

Benzer problemler

• Container With Most Water (LeetCode 11) (bu sette: container-with-most-water).
• Trapping Rain Water II (LeetCode 407).
• Largest Rectangle in Histogram (LeetCode 84): monoton stack.
• Daily Temperatures (LeetCode 739): monoton stack temeli (bu sette: daily-temperatures).