Stos monotoniczny: następny większy element

Dla każdej liczby należy znaleźć pierwszą większą wartość po jej prawej stronie. Brute force wymaga O(n²), ale stos monotoniczny rozwiązuje ten problem w jednym przejściu.

Stos monotoniczny przechowuje wartości w uporządkowanej kolejności, tutaj malejącej, więc w chwili naruszenia tego porządku wiadomo, że znaleziono odpowiedź.

Odkładaj na stos indeksy, a nie same liczby. Dzięki temu dokładnie wiadomo, którą pozycję uzupełnić, gdy pojawi się większy element.

Przejdź po tablicy jeden raz. Przy każdym indeksie zdejmiesz rozwiązane elementy ze stosu albo odłożysz bieżący indeks do późniejszego rozpatrzenia.

Dopóki bieżąca wartość jest większa od wartości na indeksie znajdującym się na szczycie, ten element na szczycie właśnie znalazł swój następny większy element.

Zdejmij indeks ze szczytu i ustaw jego odpowiedź na bieżącą wartość. Każdy indeks zostaje rozstrzygnięty dokładnie raz, dzięki czemu praca ma charakter liniowy.

Po rozstrzygnięciu wszystkich mniejszych elementów odłóż bieżący indeks, aby mógł poczekać na swój przyszły większy element.

Indeksy pozostające na stosie na końcu nigdy nie napotkały większej wartości. Zachowują domyślną wartość -1, która oznacza, że taki element nie istnieje.

Każdy indeks zostaje dodany raz i zdjęty raz. Nawet z wewnętrzną pętlą while całkowity nakład pracy dla całego przejścia pozostaje liniowy.

Potrzebny jest następny mniejszy element? Utrzymuj stos rosnący, odwracając porównanie z większe niż na mniejsze niż.

Zapytania o rozpiętość, ceny akcji i pola histogramów korzystają z tej samej idei. Stos monotoniczny to podstawowy schemat konkursowy, który warto zapamiętać.

Użyli Państwo malejącego stosu monotonicznego indeksów, aby znaleźć następne większe elementy w czasie O(n). Ten schemat otwiera drogę do rozwiązania wielu problemów dotyczących rozpiętości. 🚀