Monotonic Stack & Deque

Concept

A monotonic stack stays increasing or decreasing. When a new element breaks the order, you pop — and each pop is the moment you discover an answer for the popped element (e.g. its next greater element).

A monotonic deque keeps candidates for a sliding-window maximum: drop smaller elements from the back, drop expired indices from the front. The front is always the window max.

Every element is pushed and popped at most once, so total time is O(n) even with a nested while loop.

Complexity

Code (Python)

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

from collections import deque
def max_sliding_window(nums, k):
    dq, out = 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:
            out.append(nums[dq[0]])
    return out

Remember

• Store indices, not values — you often need distances.
• 'Next greater/smaller', 'span', 'temperatures' → monotonic stack.
• 'Max/min of every window' → monotonic deque.