# Monotonic Stack / Queue — Data Structures & Algorithms

Source: https://www.geekswithgeeks.com/en/dsa/monotonic-stack

> A stack or deque kept in increasing or decreasing order to answer next-greater and sliding-window-min/max in O(n).

## Keep it ordered

A **monotonic stack** only pushes elements that keep the stack increasing (or decreasing). Before pushing, pop everything that violates the order. Each element is pushed and popped at most once, giving `O(n)` total for problems that look `O(n^2)` at first glance.

## Next greater element

Scan right to left (or left to right with indices). Pop smaller elements before pushing — whoever remains on top is the next greater.

```python
def next_greater(nums):
    res = [-1] * len(nums)
    stack = []  # indices, values decreasing bottom to top
    for i, x in enumerate(nums):
        while stack and nums[stack[-1]] < x:
            res[stack.pop()] = x
        stack.append(i)
    return res
```

Output:

```
next_greater([2, 1, 2, 4, 3])
# [4, 2, 4, -1, -1]
```

## Sliding window maximum

A **monotonic deque** of indices keeps the window's max at the front. Drop indices that fall out of the window, and pop smaller trailing values before appending.

```python
from collections import deque

def max_sliding_window(nums, k):
    dq, res = deque(), []
    for i, x in enumerate(nums):
        while dq and nums[dq[-1]] <= x:
            dq.pop()
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()
        if i >= k - 1:
            res.append(nums[dq[0]])
    return res
```

## Spot the pattern

Reach for a monotonic stack/queue for: next greater/smaller element, largest rectangle in histogram, sliding window max/min, and stock-span style problems.