Monotonic Structures: Next Greater Element & Sliding Window Maximum
Master monotonic data structures. Learn how Monotonic Stacks solve Next Greater Element in O(N) time and Monotonic Queues find Sliding Window Maximums.
By the end, you’ll be able to…
- Construct Monotonic Increasing and Decreasing Stacks.
- Solve the 'Next Greater Element' problem in O(N) time using a Monotonic Stack.
- Implement a Monotonic Queue to solve 'Sliding Window Maximum' in linear time.
01What is a Monotonic Stack?
A Monotonic Stack is a stack whose elements are strictly maintained in sorted order (either monotonically increasing or monotonically decreasing).
When pushing a new element X onto a Monotonic Decreasing Stack, we first pop all elements from the stack that are smaller than or equal to X. Because smaller elements are popped before X is pushed, X becomes the Next Greater Element for all those popped nodes! Each element is pushed once and popped at most once, reducing problems from O(N^2) to linear O(N) time.
02Dry-Run Trace Table for Next Greater Element
Let us trace the algorithm on nums = [2, 1, 2, 4, 3]:
Notice how index 3 (value 4) pops both 2 and 1 in sequence, resolving their next greater elements in O(1) amortized time.
+-----+-----+-----------+---------------+------------------+-----------------+| i | num | Stack Top | Stack Action | Result Update | Stack State |+-----+-----+-----------+---------------+------------------+-----------------+| 0 | 2 | empty | push(0) | - | [0 (val 2)] || 1 | 1 | 2 > 1 | push(1) | - | [0, 1 (val 1)] || 2 | 2 | 1 < 2 | pop(1),push(2)| res[1] = 2 | [0, 2 (val 2)] || 3 | 4 | 2 < 4 | pop(2),pop(0) | res[2]=4,res[0]=4| [3 (val 4)] || 4 | 3 | 4 > 3 | push(4) | - | [3, 4 (val 3)] |+-----+-----+-----------+---------------+------------------+-----------------+Final Result: [4, 2, 4, -1, -1]! Computed in O(N) time!03The Monotonic Deque: Sliding Window Maximum
In the 'Sliding Window Maximum' problem, we find the maximum element in every sliding window of size K. A naive search in each window takes O(N * K) time. A max-heap takes O(N log K).
Using a Monotonic Deque (ArrayDeque), we maintain indices of elements in strictly descending order. At each step: 1) Pop elements from the back that are smaller than the incoming element (they can never be the maximum). 2) Discard the front element if it slid out of the window. 3) The front of the deque is ALWAYS the maximum of the current window! This achieves optimal O(N) time.
04Why This Matters in Production
Monotonic structures are the backbone of financial technical analysis indicators (e.g. Bollinger Bands, rolling highs/lows over market ticks) and graphics engines (calculating visible skyline polygons in 3D gaming).
By discarding suboptimal elements immediately, the monotonic deque processes gigabytes of real-time market data with strict linear O(N) execution time, eliminating latency jitter.
05Production Architecture & Engineering Trade-Offs
When selecting data structures for high-concurrency environments, developers must analyze both time complexity and memory overhead. Standard collection classes wrap primitive values in heap-allocated wrapper objects, introducing substantial pointer overhead and degrading CPU cache locality. In high-frequency messaging pipelines, storing millions of boxed integers in an ArrayList creates gigabytes of object overhead that stresses garbage collection cycles.
To achieve predictable low-latency throughput, production systems favor primitive-specialized collections or contiguous off-heap direct buffers. Additionally, when using ConcurrentHashMap, choosing the appropriate initial capacity and load factor avoids expensive table rehashing and concurrent bucket redistribution during peak transaction surges.
The ideas worth keeping.
- Monotonic stacks maintain elements in sorted order to find next/previous greater/smaller elements in O(N) time.
- Each element is pushed once and popped once, guaranteeing linear amortized complexity.
- Monotonic deques solve Sliding Window Maximum in O(N) time by keeping window candidates in descending order.
Make it yours.
Type and test your code right here in the interactive workspace. Run your solution, check the output, and compare with the worked guide when ready.
Exercise 1: Daily Temperatures Problem
Given temperatures = [73, 74, 75, 71, 69, 72, 76, 73], explain how a monotonic stack calculates how many days until a warmer temperature in O(N) time.
Explore a worked solution
Maintain stack of indices. For each day, pop while current temp > stack.peek() temp. The waiting days is currentIndex - poppedIndex. Push currentIndex. Un-popped days stay 0.The difference between indices represents the exact day count to the next warmer temperature.
Exercise 2: Largest Rectangle in Histogram
Outline how a monotonic increasing stack finds the largest rectangular area in a histogram in O(N) time.
Explore a worked solution
Stack stores indices of increasing heights. When a shorter bar appears, pop the taller bar; its height is height[popped], and width is current_i - stack.peek() - 1. Update max area.Popping determines both the left and right boundaries of the maximum rectangle for that bar in O(N) time.
What stayed with you?
Check the ideas while they’re fresh. Your answers stay in this page and feedback appears as you go.
Exercise 1: Daily Temperatures Problem
Given temperatures = [73, 74, 75, 71, 69, 72, 76, 73], explain how a monotonic stack calculates how many days until a warmer temperature in O(N) time.
Build successful. (Java 15) [Process exited normally]
Keep exploring.
The official references behind this lesson, when you want a second angle or the full details.
One lesson closer.
Reading is a start. Trying it yourself makes the connection.