Monotonic stack

Question 1

What is the definition of a Monotonic Stack?

Answer 1

Maintains stack in increasing/decreasing order for comparisons.

Question 2

When is a Monotonic Stack used?

Answer 2

Next/previous greater/smaller elements.

Question 3

What are the key steps in using a Monotonic Stack?

Answer 3

1. Initialize empty stack.
2. Pop stack while top violates monotonicity.
3. Push current element, update result.

Question 4

How does a Monotonic Stack apply to Asteroid Collision?

Answer 4

Simulate asteroid collisions using stack to track asteroids, pop if collision destroys smaller.

Question 5

What is the complexity of a Monotonic Stack?

Answer 5

Time: O(n), Space: O(n).

Question 6

What are some gotchas when using a Monotonic Stack?

Answer 6

Empty stack, same-size collisions.

Question 7

Provide a code example for a Monotonic Stack.

Answer 7

```python
from typing import List
def asteroid_collision(asteroids: List[int]) -> List[int]:
stack: List[int] = []
for asteroid in asteroids:
while True:
if not stack or asteroid > 0 or stack[-1] < 0:
stack.append(asteroid)
break
if stack[-1] == -asteroid:
stack.pop()
break
if stack[-1] > -asteroid:
break
stack.pop()
return stack
~~~

Question 8

What is a visual representation for a Monotonic Stack?

Answer 8

[Add image manually].