Última atividade 1794541558

Interview prep notes

linkjobai revisou este gist 1794541557. Ir para a revisão

1 file changed, 42 insertions

monotonic-stack.md(arquivo criado)

@@ -0,0 +1,42 @@
1 + # Monotonic Stack: The Pattern Behind "Next Greater Element" Questions
2 +
3 + If a question asks for the **next greater**, **previous smaller**, or "how many days until a warmer temperature", a monotonic stack usually turns an O(n²) scan into O(n).
4 +
5 + ## Core idea
6 +
7 + Keep a stack of indices whose values are in sorted order (decreasing for "next greater"). When a new value breaks the order, it is the answer for every index you pop.
8 +
9 + ```python
10 + def daily_temperatures(temps): # LeetCode 739
11 + ans = [0] * len(temps)
12 + stack = [] # indices, temps decreasing
13 + for i, t in enumerate(temps):
14 + while stack and temps[stack[-1]] < t:
15 + j = stack.pop()
16 + ans[j] = i - j
17 + stack.append(i)
18 + return ans
19 + ```
20 +
21 + Each index is pushed and popped at most once, so the loop is O(n) even with the inner `while`.
22 +
23 + ## Choosing the direction
24 +
25 + | Question asks for | Stack keeps values | Pop when new value is |
26 + |---|---|---|
27 + | Next greater | decreasing | greater |
28 + | Next smaller | increasing | smaller |
29 + | Previous greater | decreasing | greater or equal (answer = new top) |
30 +
31 + ## Harder problems that use it
32 +
33 + - **Largest Rectangle in Histogram (84):** increasing stack; when a bar is popped, its width runs from the new stack top to the current index.
34 + - **Trapping Rain Water (42):** popping a lower bar between two taller ones gives the water above it.
35 + - **Sum of Subarray Minimums (907):** previous-smaller and next-smaller distances give how many subarrays each element is the minimum of. Handle duplicates with `<` on one side and `<=` on the other.
36 +
37 + ## How to explain it in the interview
38 +
39 + Say *why* it is linear: "Every element enters and leaves the stack once." Then trace a 5-element example on the whiteboard; interviewers care more about the invariant than the code.
40 +
41 + ---
42 + *Disclosure: I work on [Linkjob AI's coding interview assistant](https://www.linkjob.ai/coding-interview-copilot/). This write-up is general practice material.*
Próximo Anterior