Stacks and queues · 2 of 2
Monotonic stack
Find the next warmer day, the nearest smaller value and the maximum of every window in one pass each, by popping the entries a new value makes useless.
Books1
Links3
- Stacks Solves CSES Nearest Smaller Values with a stack of (value, index) pairs, then lists graded problems that use a monotonic stack. usaco.guide (opens in a new tab)
- Sliding Window Its last section finds the sliding window maximum in linear time twice, with a monotonic deque and with two stacks that each store a maximum. usaco.guide (opens in a new tab)
- 单调栈 (Monotonic stack) How a monotonic stack inserts by popping, an application that records where each element is popped, and practice problems. oi-wiki.org (opens in a new tab)