Base Monotonic Deque

When To Use

Use this when you need the best max/min candidate among active indices.

The deque stores indices. Values are read from the original array.

For maximum queries, keep values decreasing:

push_max(i):
    while dq not empty and nums[dq.back] <= nums[i]:
        dq.pop_back()
 
    dq.push_back(i)

For minimum queries, keep values increasing:

push_min(i):
    while dq not empty and nums[dq.back] >= nums[i]:
        dq.pop_back()
 
    dq.push_back(i)

After pushing, the best active candidate is always at dq.front.

Use this when the left boundary moves.

expire(l):
    if dq not empty and dq.front < l:
        dq.pop_front()

For one-step movement, this also works:

remove_left(l):
    if dq not empty and dq.front == l:
        dq.pop_front()

When a newer index has a better value than an older index, the older index can never be useful again while both are active.