TOPIC: Monotonic Stack

DEFINITION: A monotonic stack is a data structure that maintains a stack of elements in either monotonically increasing or decreasing order, allowing for efficient retrieval of the next larger or smaller element. This data structure is particularly useful in solving problems that involve finding the next greater or smaller element in a sequence. It helps in reducing the time complexity by avoiding unnecessary comparisons.

TIME_COMPLEXITY: O(n) - The best, average, and worst-case time complexities are all linear because each element is pushed and popped from the stack exactly once.

SPACE_COMPLEXITY: O(n) - The space complexity is linear because in the worst-case scenario, the stack can contain up to n elements, where n is the number of elements in the input sequence.

USE_WHEN: Use a monotonic stack when you need to find the next greater or smaller element for each element in a sequence, such as in problems involving finding the next greater element in an array. This data structure is particularly useful when the sequence is large and the elements are distinct.

AVOID_WHEN: Avoid using a monotonic stack when the sequence is very small or when the elements are mostly the same, as the overhead of maintaining the stack may outweigh its benefits; in such cases, a simple iterative approach might be more efficient.

EXAMPLE:
Consider the sequence [3, 1, 2, 4] and we want to find the next greater element for each element.
- Start with an empty stack: []
- Push 3: [3]
- Push 1: [3, 1] (since 1 < 3, we don't pop)
- Push 2: [3, 1, 2] (since 2 > 1, pop 1 and update next greater for 1 as 2) -> [3, 2]
- Push 4: [3, 2, 4] (since 4 > 2, pop 2 and update next greater for 2 as 4) -> [3, 4] (since 4 > 3, pop 3 and update next greater for 3 as 4) -> [4]
- Result: Next greater elements are [4, 2, 4, -1] (assuming -1 for the last element since there's no greater element after it) 
 

REAL_WORLD_ANALOGY: A monotonic stack can be thought of as a pile of plates where each plate is either larger or smaller than the one below it, and you're trying to find the next larger or smaller plate for each one in the pile.

SOURCE_NOTE: Concepts referenced from general data structures and algorithms principles.