Verem és monoton stack

A stack a vezérlési logikát adatstruktúrává alakítja: LIFO működést modellez, megmutatja a rejtett egymásba ágyazottságot, és különösen erős lesz akkor, amikor egy monoton invariáns egyetlen passzban old meg "next greater", "next smaller" és hasonló boundary feladatokat.

---

1. Definíció

Mi az a stack?

A stack egy Last-In, First-Out adatstruktúra. Az utoljára betett elem jön ki először. Az alapműveletek: push, pop, peek és gyakran isEmpty.

Miért létezik?

A stack azért hasznos, mert sok probléma természetesen a legutóbbi feloldatlan elemre épül.

Ez előjön például:

• egymásba ágyazott struktúráknál,
• undo-szerű folyamatoknál,
• rekurziónál,
• expression parsingnál,
• és olyan mintáknál, ahol egy elem "vár" egy későbbi erősebb párra.

Mi az a monoton stack?

A monotonic stack egy olyan stack, amely rendezési invariánst tart fenn — tipikusan increasing vagy decreasing formában. Itt a stack nem pusztán értékeket tárol, hanem olyan candidate-eket, amelyek egy adott sorrendi szabály mellett továbbra is relevánsak.

Hova illik?

Ez a téma akkor fontos, ha a feladat ilyesmit kér:

• balanced parentheses,
• nearest greater element,
• nearest smaller element,
• daily temperatures,
• stock span,
• histogram boundary gondolkodás,
• vagy bármilyen helyzet, ahol minden elemhez a következő vagy előző olyan elemet keresed, amely megszegi a jelenlegi feltételt.

Intuíció

A sima stack olyan, mint egy tányérhalom.

Mindig felülről veszel le.

A monotonic stack olyan tányérhalom, ahol folyamatosan kiszórod azokat az elemeket, amelyek már biztosan nem lesznek hasznosak.

Nem csak tárol.

Szűr is.

Java kontextus

Java interjúkódban stack viselkedéshez Deque ajánlott.

A gyakorlati alapértelmezett választás általában az ArrayDeque.

Példa:

Deque<Integer> stack = new ArrayDeque<>();
stack.push(10);
stack.push(20);
int top = stack.peek();
int removed = stack.pop();

A régi Stack osztály létezik, de modern Java kódban általában nem ez a preferált API.

---

2. Alapfogalmak

2.1 LIFO működés

A stack definíciójának lényege a LIFO.

Ezért ideális, ha a legutóbb megjelent feloldatlan elemre kell először reagálni.

Példák:

• zárójelek,
• rekurzív hívások,
• path backtracking,
• undo history.

2.2 Alapműveletek és komplexitás

2.3 Miért jó a stack egymásba ágyazottságra?

Ha valami megnyílik és később zárul, akkor a legutóbb megnyitott elem zárul le először.

Ez pontosan LIFO viselkedés.

A balanced parentheses ennek a legtisztább példája.

Amikor zárójelet látsz, a legutóbbi feloldatlan nyitójelet kell vele párosítani.

2.4 Stack és rekurzió

A rekurzió call stackje szintén stack.

Ezért a rekurzív DFS és az explicit stackes DFS nagyon közeli gondolatmenet.

Interjún jó jel, ha ezt észreveszed.

2.5 Monoton invariáns

A monotonic stack pluszban fenntart egy rendezési szabályt.

Decreasing stack esetén:

• az értékek alulról felfelé csökkenők maradnak,
• a kisebb elemek kipottyannak, ha nagyobb érkezik.

Increasing stack esetén:

• az értékek alulról felfelé növekvők,
• a nagyobb elemek kipottyannak, ha kisebb érkezik.

A pontos irányt a feladat dönti el.

2.6 Miért erős a monoton stack?

Sok olyan feladatot tesz lineárissá, amely elsőre kvadratikusnak látszik.

Naiv megközelítés:

• minden indexből jobbra nézel addig, amíg találsz megfelelő elemet.

Ez gyakran O(n^2).

Monotonic stack megközelítés:

• csak a még feloldatlan candidate-eket tartod meg,
• azokat oldod fel, amikor megérkezik egy erősebb elem,
• minden elem egyszer kerül be és egyszer kerül ki.

Így O(n) lesz.

2.7 Érték vagy index?

Nagyon fontos döntés, hogy értéket vagy indexet tárolsz-e.

Sok monotonic stack feladatban indexet kell tárolni, nem értéket.

Miért jobb gyakran az index?

• távolságot tudsz számolni,
• vissza tudsz olvasni az eredeti tömbből,
• duplikátumokat is jobban kezeled.

Például Daily Temperatures esetén a válasz különbség két pozíció között, ezért az index a természetes state.

2.8 Previous vs next variációk

Négy gyakori változat van:

• next greater,
• next smaller,
• previous greater,
• previous smaller.

A ciklus iránya és a pop feltétel változik, de a fő minta ugyanaz.

2.9 Az egyenlőség kezelése számít

Nagyon gyakori hiba, hogy rossz az összehasonlító operátor.

Lehet, hogy a pop feltételnek ez kell:

• <,
• <=,
• >,
• vagy >=.

Ez attól függ, hogy az egyenlő elemek maradjanak-e a stackben.

Ez nem stíluskérdés.

A helyességet befolyásolja.

2.10 Felismerési jelek

A monotonic stack legyen gyanús, ha:

• a feladat a következő vagy előző erősebb/gyengébb elemről szól,
• a brute force minden pozícióból újra szkennel jobbra vagy balra,
• a válasz nearest boundary jellegű,
• vagy minden elem egy jobb jövőbeli partnerre vár.

2.11 Amortizált gondolkodás

A monotonic stack megoldások kulcsa gyakran az amortizált komplexitás.

Lehet, hogy egy iteráció sok popot végez.

De minden elem legfeljebb egyszer kerül be és legfeljebb egyszer kerül ki.

Ezért a teljes stackmunka a teljes inputra lineáris.

---

3. Gyakorlati használat

Mikor jó a sima stack?

A stack akkor jó, ha a feladat a következőkről szól:

• nested struktúrák párosítása,
• undo-szerű viselkedés,
• backtracking támogatás,
• iteratív DFS,
• expression evaluation.

Klasszikus példák:

• valid parentheses,
• simplify path,
• browser history modell,
• DFS rekurzió nélkül.

Mikor jó a monotonic stack?

A monotonic stack akkor jó, ha a feladat nearest boundary logikát kér valamilyen sorrendi szabállyal.

Tipikus példák:

• next greater element,
• daily temperatures,
• stock span,
• largest rectangle in histogram,
• trapping vagy range boundary előkészítés,
• gyengébb candidate-ek online eldobjása.

Mikor NEM jó a stack?

Ne erőltesd a stacket, ha:

• a probléma alapvetően FIFO,
• a rendezés egyszerűbb megoldást ad,
• a prefix sum vagy two pointers természetesebb,
• vagy nincs szükség a "legutóbbi feloldatlan elem" logikára.

Java-specifikus tanács

Ajánlott minta:

Deque<Integer> stack = new ArrayDeque<>();

A régi Stack osztályt a legtöbb modern Java interjúkódban kerüld.

Monotonic stackhez is általában ArrayDeque<Integer> a jó alap.

Pair-programming nézőpont

Egy erős magyarázat így hangzik:

• "Csökkenő monotonic stacket használok indexekkel."
• "Amíg az aktuális érték nagyobb, mint a stack tetején álló indexhez tartozó érték, addig fel tudom oldani a várakozó elemeket."
• "Minden index egyszer kerül be és egyszer kerül ki, ezért a teljes költség lineáris."

Ez sokkal erősebb, mint annyi, hogy "ez monotonic stack feladat".

Kapcsolódó LeetCode feladatok

• LeetCode #20 — Valid Parentheses — klasszikus stack-matching gyakorlat.
• LeetCode #739 — Daily Temperatures — monotonic decreasing stack indexkövetéssel.
• LeetCode #496 — Next Greater Element I — monotonic stack + HashMap lookup-hoz.
• LeetCode #84 — Largest Rectangle in Histogram — monotonic stack span-számoláshoz.
• LeetCode #155 — Min Stack — segéd-stack a running minimum karbantartásához.

---

4. Kódpéldák

Alap példa

Ez a példa zárójeleket validál stackkel.

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Map;

public class ValidParenthesesExample {
    public static boolean isValid(String text) {
        Deque<Character> stack = new ArrayDeque<>();
        Map<Character, Character> closingToOpening = Map.of(
                ')', '(',
                ']', '[',
                '}', '{'
        );

        for (char current : text.toCharArray()) {
            if (current == '(' || current == '[' || current == '{') {
                stack.push(current);
            } else {
                if (stack.isEmpty() || stack.pop() != closingToOpening.get(current)) {
                    return false;
                }
            }
        }

        return stack.isEmpty();
    }
}

Miért működik?

• a nyitójelek feloldatlan munkaelemek,
• a zárójelnek a legutóbbi feloldatlan nyitójelet kell lezárnia,
• ha a végén marad valami a stackben, akkor a szerkezet hiányos.

Haladó példa

Ez a példa monotonic stackkel oldja meg a Next Greater Element problémát jobbra.

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

public class NextGreaterElementExample {
    public static int[] nextGreater(int[] nums) {
        int[] answer = new int[nums.length];
        Arrays.fill(answer, -1);

        Deque<Integer> stack = new ArrayDeque<>();

        for (int index = 0; index < nums.length; index++) {
            while (!stack.isEmpty() && nums[index] > nums[stack.peek()]) {
                int resolvedIndex = stack.pop();
                answer[resolvedIndex] = nums[index];
            }
            stack.push(index);
        }

        return answer;
    }
}

Kulcs invariáns:

• a stack olyan indexeket tart, amelyekhez még nincs meg a következő nagyobb elem,
• ezekhez az indexekhez az értékek a választott szabály szerint monotonok,
• az aktuális érték feloldja a gyengébb candidate-eket.

Tipikus hiba

Ez a verzió értékeket tárol indexek helyett egy távolság-alapú feladatban.

import java.util.ArrayDeque;
import java.util.Deque;

public class BrokenDailyTemperaturesIdea {
    public static void broken(int[] temperatures) {
        Deque<Integer> stack = new ArrayDeque<>();

        for (int temperature : temperatures) {
            while (!stack.isEmpty() && temperature > stack.peek()) {
                stack.pop();
            }
            stack.push(temperature);
        }
    }
}

Miért hibás?

• az érték önmagában nem mondja meg, melyik nap várakozik,
• ezért nem tudsz távolságot számolni,
• és a duplikátumok is kétértelművé válnak.

Ha distance vagy boundary kimenet kell, az index szinte mindig jobb state.

Még egy hasznos minta: Daily Temperatures

import java.util.ArrayDeque;
import java.util.Deque;

public class DailyTemperaturesExample {
    public static int[] solve(int[] temperatures) {
        int[] answer = new int[temperatures.length];
        Deque<Integer> stack = new ArrayDeque<>();

        for (int index = 0; index < temperatures.length; index++) {
            while (!stack.isEmpty() && temperatures[index] > temperatures[stack.peek()]) {
                int previousIndex = stack.pop();
                answer[previousIndex] = index - previousIndex;
            }
            stack.push(index);
        }

        return answer;
    }
}

Ez az egyik legtisztább interjús demonstráció arra, hogy miért értékes a monotonic stack.

---

5. Trade-offok

Teljesítménybeli árnyalat

A monotonic stack nem varázslat.

Azért működik, mert minden elem korlátozott számú alkalommal vesz részt a folyamatban.

Ha nem tudod kimondani a "push once, pop once" történetet, még nem teljesen a tiéd a minta.

Memóriabeli árnyalat

Az extra stack tipikusan az a trade-off, amit azért vállalsz, hogy ne kelljen újra és újra szkennelni a tömböt.

Ez sokszor nagyon jó csere.

Olvashatósági árnyalat

Az olvasóknak jellemzően a while feltétel a legnehezebb része.

Mondd ki az invariánst.

Például:

• "decreasing stack of indices waiting for a greater value",
• "increasing stack of candidate minima",
• "open brackets waiting to be closed".

---

6. Gyakori hibák

1. Rossz API-t használsz — Java-ban sokan még mindig Stack-et használnak Deque helyett. Modern alapértelmezettként általában ArrayDeque kell.
2. Értéket tárolsz index helyett — Ha a válasz távolság vagy pozíciófüggő, a value-only state elrontja a megoldást.
3. Rossz a pop feltétel — > kontra >= vagy < kontra <= megváltoztatja a duplikátumok kezelését.
4. Nem gondolod végig a maradék elemeket — Next-greater jellegű feladatokban a fel nem oldott elemek jellemzően default választ kapnak, például -1 vagy 0.
5. Nem mondod ki az invariánst — Invariáns nélkül a kód könnyen bemagolt sémává válik valódi megértés helyett.
6. Összekevered a FIFO és LIFO logikát — Van, hogy queue kell, nem stack. Ha a legrégebbi elemnek kell először sorra kerülnie, a stack rossz modell.
7. Túl korán vagy túl későn pusholsz — Sok monotonic megoldásban a "oldd fel, amit kell, aztán pushold az aktuálisat" sorrend elengedhetetlen.

Debug tipp

Rajzold vagy írasd ki a stack tartalmát minden lépés után egy pici inputon.

Ha nem tudod megindokolni, miért marad ott a tetején egy elem, akkor valószínűleg rossz az invariáns.

---

7. Mélyebb összefüggések

Miért ennyire alapfeladat a balanced parentheses?

Mert szinte zaj nélkül mutatja meg a tiszta LIFO logikát.

Megtanítja, hogy:

• a feloldatlan nyitóelemek jelentik az állapotot,
• a legutóbbi feloldatlan elem számít,
• és csak akkor korrekt a szerkezet, ha a végén semmi sem marad.

Ugyanez a logika később parser és traversal feladatokban is visszajön.

Miért tűnik elsőre furcsának a monotonic stack?

Mert itt a stack nem csak az időrendi történetet modellezi.

Hanem feloldatlan candidate-eket tart fenn egy rendezési szabály szerint.

Nem mindent tárolsz.

Csak azt, ami még képes befolyásolni egy későbbi választ.

A monotonic stack egy online szűrő

Ez nagyon hasznos mentális modell.

Amikor megérkezik egy új elem:

• a gyengébb candidate-ek kiesnek,
• az erősebb, még releváns candidate-ek bent maradnak,
• és az új elem csak akkor kerül be, ha a jövőre nézve még számíthat.

Ezért érződik egyszerre greedy-nek és struktúrált mintának.

Az egyenlőség gyakran a valódi csapda

Gondolj a duplikátumokra.

Az egyenlő értékek feloldják egymást?

Néha igen.

Néha nem.

Pont ezért kevés az, hogy "ismerem a monotonic stack template-et".

A probléma jelentéséből kell levezetni az összehasonlító operátort.

Largest Rectangle in Histogram kapcsolat

A histogram boundary és area feladatoknál a monotonic stack még mélyebb lesz.

Ott a stack már nem csak next greater/smaller választ ad.

Hanem maximális szakaszokat határoz meg, ahol egy adott oszlop még limitáló magasság marad.

Ugyanaz az invariáns, csak összetettebb következménnyel.

Pair-programming helyzet

Tegyük fel, hogy Daily Temperatures-t magyarázol.

Egy erős narratíva:

• minden nap egy melegebb jövőbeli napra vár,
• a stack a várakozó napok indexeit tárolja,
• ezekhez az indexekhez a hőmérsékletek monotonok,
• egy melegebb nap feloldja a tetején lévő gyengébb várakozókat,
• minden index egyszer kerül be és egyszer kerül ki,
• ezért a megoldás lineáris.

Ez tulajdonosi szintű magyarázat, nem bemagolt sablon.

---

8. Interjúkérdések

Q: Miért a stack a jó adatstruktúra balanced parentheses-re? — A: Mert a zárójelnek a legutóbbi feloldatlan nyitójelet kell párosítania. Ez pontosan LIFO viselkedés.

Q: Miért tárol sok monotonic stack feladat indexet érték helyett? — A: Mert indexből lehet távolságot számolni, vissza lehet olvasni az eredeti értéket, és a duplikátumok is biztonságosabban kezelhetők.

Q: Miért lesz sok monotonic stack megoldás O(n) és nem O(n^2)? — A: Mert minden elem legfeljebb egyszer kerül be és egyszer kerül ki a stackből, így a teljes stackmunka lineáris marad.

Q: Mi a monotonic stack helyességének legnehezebb része? — A: A megfelelő invariáns és összehasonlító feltétel kiválasztása, főleg duplikátumok jelenlétében.

Q: Miért jobb Java interjúkódban általában Deque-ot használni Stack helyett? — A: Mert a Deque + ArrayDeque modernebb és jellemzően ajánlottabb API a stack-szemantika modellezésére.

---

9. Fogalomtár

---

10. Cheatsheet

• Stacket akkor használj, ha a legutóbbi feloldatlan elem számít a legtöbbet.
• Java-ban stack viselkedéshez Deque / ArrayDeque az alapértelmezett.
• A balanced parentheses a legtisztább LIFO példa.
• A monotonic stack nearest-boundary feladatokat old meg hatékonyan.
• Sok monotonic feladatnál indexet kell tárolni, nem értéket.
• Mondd ki az invariánst: növekvő vagy csökkenő, értékek vagy indexek, mire várnak?
• Duplikátumoknál különösen figyelj az összehasonlító operátorra.
• A "push once, pop once" az amortizált komplexitás kulcstörténete.
• Ha a legrégebbi elem számít először, akkor valószínűleg queue kell, nem stack.
• Ha nem tudod megindokolni, miért marad valami a stack tetején, még nem stabil az invariáns.