Tekdüze Yığın: Sonraki Büyük Öğe

Her sayı için sağındaki ilk daha büyük değeri bulmak istersiniz. Kaba kuvvet O(n kare) sürer, ancak bir monotonik yığın bunu tek geçişte yapar.

Monotonik yığın, değerlerini sıralı biçimde, burada azalan sırada tutar; böylece bu sıra bozulacağı anda bir yanıtın bulunduğunu anlarız.

Ham sayılar yerine dizinleri yığına itin. Böylece daha büyük bir öğe ortaya çıktığında tam olarak hangi konumu dolduracağınızı bilirsiniz.

Dizinin üzerinden bir kez geçin. Her dizinde ya sonucu belirlenmiş öğeleri çıkarırsınız ya da geçerli dizini daha sonrası için yığına itersiniz.

Geçerli değer, üstteki dizindeki değerden büyük olduğu sürece, o üstteki öğe sonunda kendisinden sonraki daha büyük öğeyi bulmuş demektir.

Üstteki dizini çıkarın ve yanıtını geçerli değere ayarlayın. Her dizin tam olarak bir kez çözümlendiği için iş yükü doğrusal kalır.

Daha küçük olanların tümünü çözdükten sonra geçerli dizini yığına itin; böylece kendisi için ilerideki daha büyük öğeyi bekleyebilir.

Sonunda hâlâ yığında bulunan dizinler daha büyük bir değerle hiç karşılaşmamıştır. Varsayılan değerleri -1 olarak kalır; bu da böyle bir değerin bulunmadığı anlamına gelir.

Her dizin bir kez yığına itilir ve bir kez çıkarılır. İçteki while döngüsüne rağmen toplam iş yükü tüm tarama boyunca doğrusal kalır.

Bunun yerine bir sonraki daha küçük öğeyi mi arıyorsunuz? Büyükten küçüğe karşılaştırmayı çevirerek yığını artan sırada tutun.

Aralık sorguları, hisse senedi fiyatları ve histogram alanlarının tümü bu fikri yeniden kullanır. Monotonik yığın, ezberlemeye değer temel bir yarışma örüntüsüdür.

Bir sonraki daha büyük öğeyi monotonik yığınla buluyorsunuz. Toplam çalışma süresi neden doğrusaldır?

Bir sonraki daha büyük öğeleri O(n) zamanda bulmak için dizinlerden oluşan azalan bir monotonik yığın kullandınız. Bu örüntü birçok aralık problemini çözmenizi sağlar. 🚀