linkjobai 修订了这个 Gist . 转到此修订
1 file changed, 42 insertions
monotonic-stack.md(文件已创建)
| @@ -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.* | |
上一页
下一页