Monotonic Queue to Solve Sliding Window Problems
This article will resolve
LeetCode | Difficulty |
---|---|
239. Sliding Window Maximum | 🔴 |
Prerequisite Knowledge
Before reading this article, you should first learn:
In a previous article Solving Three Algorithm Problems Using Monotonic Stack, we introduced the special data structure called monotonic stack. Here, we will discuss a similar data structure called "monotonic queue."
You might not have heard of this data structure before. Essentially, it is just a "queue" that uses a clever method to ensure that the elements in the queue are all monotonically increasing (or decreasing).
Why invent a structure like the "monotonic queue"? It is mainly to solve the following scenario:
Given an array window
with a known extreme value A
, if you add a number B
to window
, you can immediately calculate the new extreme value by comparing A
and B
. However, if you remove a number from window
, you cannot directly obtain the extreme value. If the removed number happens to be A
, you need to traverse all elements in window
to find the new extreme value.
This scenario is common, but it seems that a monotonic queue is not necessary. For example, a priority queue (binary heap) is specifically designed for dynamically finding extreme values. By creating a max (min) heap, you can quickly get the maximum (minimum) value, right?
For simply maintaining the extreme values, a priority queue is professional, with the head of the queue being the extreme value. However, a priority queue cannot satisfy the standard "first-in, first-out" time sequence of a queue structure. This is because a priority queue uses a binary heap to dynamically sort elements, and the order of dequeue is determined by the element size, having no relation to the order of enqueue.
Thus, a new queue structure is needed that can both maintain the "first-in, first-out" time sequence of queue elements and correctly maintain the extreme values of all elements in the queue, which is the "monotonic queue" structure.
The "monotonic queue" is mainly used to assist in solving problems related to sliding windows. In the previous article Core Framework of Sliding Window, the sliding window algorithm is explained as a part of the double pointer technique. However, some slightly more complex sliding window problems cannot be solved with just two pointers and require more advanced data structures.
For instance, in the previous article Core Framework of Sliding Window, for each problem discussed, whenever the window is expanded (right++
) or contracted (left++
), you can decide whether to update the answer based solely on the elements entering and leaving the window.
But in the example at the beginning of this article about determining the extreme value in a window, you cannot update the extreme value of the window based solely on the element leaving the window, unless you traverse all elements again, which increases the time complexity, something we do not want to see.
Let's look at LeetCode Problem 239 Sliding Window Maximum, which is a standard sliding window problem:
Given an array nums
and a positive integer k
, there is a window of size k
that slides from left to right across nums
. Please output the maximum value of k
elements in the window each time.
The function signature is as follows:
int[] maxSlidingWindow(int[] nums, int k);
vector<int> maxSlidingWindow(vector<int>& nums, int k);
def maxSlidingWindow(nums: List[int], k: int) -> List[int]:
func maxSlidingWindow(nums []int, k int) []int
var maxSlidingWindow = function(nums, k)
For example, here is a sample problem provided by LeetCode:
Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Explanation:
Position of the sliding window Maximum value
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
Next, we will use a monotonic queue structure to calculate the maximum value in each sliding window in time, allowing the entire algorithm to be completed in linear time.
1. Building the Solution Framework
Before introducing the API of the "monotonic queue" data structure, let's compare the standard API of a regular queue with the API implemented by the monotonic queue:
// API for a regular queue
class Queue {
// enqueue operation, add element n to the end of the queue
void push(int n);
// dequeue operation, remove the front element of the queue
void pop();
}
// API for a monotonic queue
class MonotonicQueue {
// add element n to the end of the queue
void push(int n);
// return the maximum value currently in the queue
int max();
// if the front element is n, remove it
void pop(int n);
}
// API for a regular queue
class Queue {
public:
// enqueue operation, add element n to the end of the queue
void push(int n);
// dequeue operation, remove element from the front of the queue
void pop();
};
// API for a monotonic queue
class MonotonicQueue {
public:
// add element n to the end of the queue
void push(int n);
// return the maximum value in the current queue
int max();
// remove the front element if it is n
void pop(int n);
};
# API for a regular queue
class Queue:
# enqueue operation, add element n to the end of the queue
def push(self, n: int):
pass
# dequeue operation, remove the front element of the queue
def pop(self):
pass
# API for a monotonic queue
class MonotonicQueue:
# add element n to the end of the queue
def push(self, n: int):
pass
# return the maximum value in the current queue
def max(self) -> int:
pass
# if the front element is n, remove it
def pop(self, n: int):
pass
// API of a regular queue
type Queue struct{}
// push operation, add element n to the end of the queue
func (q *Queue) push(n int) {}
// pop operation, remove the element at the front of the queue
func (q *Queue) pop() {}
// API of a monotonic queue
type MonotonicQueue struct{}
// add element n to the end of the queue
func (q *MonotonicQueue) push(n int) {}
// return the maximum value in the current queue
func (q *MonotonicQueue) max() int {}
// API for a regular queue
class Queue {
// enqueue operation, add element n to the tail of the queue
push(n) {}
// dequeue operation, remove the head element of the queue
pop() {}
};
// API for a monotonic queue
class MonotonicQueue {
// add element n to the tail of the queue
push(n) {}
// return the maximum value in the current queue
max() {}
// if the head element is n, remove it
pop(n) {}
};
Of course, the implementation of these APIs for a monotonic queue is different from a regular Queue, but for now, let's assume these operations have a time complexity of O(1) and first set up the solution framework for this "sliding window" problem:
int[] maxSlidingWindow(int[] nums, int k) {
MonotonicQueue window = new MonotonicQueue();
List<Integer> res = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
if (i < k - 1) {
// first fill the window with the first k - 1 elements
window.push(nums[i]);
} else {
// the window starts sliding forward
// move in the new element
window.push(nums[i]);
// record the maximum element in the current window to the result
res.add(window.max());
// remove the last element
window.pop(nums[i - k + 1]);
}
}
// convert the List to an int[] array as the return value
int[] arr = new int[res.size()];
for (int i = 0; i < res.size(); i++) {
arr[i] = res.get(i);
}
return arr;
}
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
MonotonicQueue window;
vector<int> res;
for (int i = 0; i < nums.size(); i++) {
if (i < k - 1) {
// first fill the window with the first k - 1 elements
window.push(nums[i]);
} else {
// the window starts to slide forward
// insert the new element
window.push(nums[i]);
// record the maximum element in the current window into the result
res.push_back(window.max());
// remove the last element
window.pop(nums[i - k + 1]);
}
}
return res;
}
from collections import deque
from typing import List
def maxSlidingWindow(nums: List[int], k: int) -> List[int]:
window = MonotonicQueue()
res = []
for i in range(len(nums)):
if i < k - 1:
# first fill the window with the first k - 1 elements
window.append(nums[i])
else:
# the window starts to slide forward
# insert the new element
window.append(nums[i])
# add the maximum element of the current window to the result
res.append(max(window))
# remove the last element
window.popleft()
# convert the List type to an int[] array as the return value
return res
func maxSlidingWindow(nums []int, k int) []int {
window := MonotonicQueue{}
var res []int
for i:=0; i<len(nums); i++ {
if i < k - 1 {
// first fill the window with the first k-1 elements
window.Push(nums[i])
} else {
// the window starts to slide forward
// add new element
window.Push(nums[i])
// record the maximum element in the current window to the result
res = append(res, window.Max())
// remove the last element
window.Pop(nums[i-k+1])
}
}
return res
}
var maxSlidingWindow = function(nums, k) {
var window = new MonotonicQueue();
var res = [];
for (var i = 0; i < nums.length; i++) {
if (i < k - 1) {
// first fill the window with the first k - 1 elements
window.push(nums[i]);
} else {
// the window starts to slide forward
// push new element
window.push(nums[i]);
// record the maximum element in the current window
res.push(window.max());
// pop the last element
window.pop(nums[i - k + 1]);
}
}
return res;
};

This idea is quite simple, right? Now let's start with the main part, the implementation of the monotonic queue.
2. Implementing the Monotonic Queue Data Structure
By observing the sliding window process, we can see that implementing a "monotonic queue" requires a data structure that supports insertion and deletion at both the head and tail. Clearly, a doubly linked list meets this requirement.
The core idea of the "monotonic queue" is similar to the "monotonic stack." The push
method still adds elements at the queue's tail, but it removes elements in front that are smaller than itself:
class MonotonicQueue {
// doubly linked list, supports quick insertion and deletion at both head and tail
// maintain elements in a monotonically increasing order from tail to head
private LinkedList<Integer> maxq = new LinkedList<>();
// add an element n at the tail, maintaining the monotonic property of maxq
public void push(int n) {
// remove all elements smaller than itself from the front
while (!maxq.isEmpty() && maxq.getLast() < n) {
maxq.pollLast();
}
maxq.addLast(n);
}
}
#include <list>
using namespace std;
class MonotonicQueue {
// doubly linked list, supports fast insertions and deletions at both ends
// maintain the elements in monotonically increasing order from tail to head
list<int> maxq;
public:
// add an element n at the tail, maintaining the monotonic property of maxq
void push(int n) {
// remove all elements smaller than itself from the front
while (!maxq.empty() && maxq.back() < n) {
maxq.pop_back();
}
maxq.push_back(n);
}
};
from collections import deque
class MonotonicQueue:
def __init__(self):
# use a deque to support adding and removing elements from both ends
# maintain the elements in increasing order from tail to head
self.maxq = deque()
# add an element n to the tail, maintaining the monotonic property of maxq
def push(self, n: int) -> None:
# remove all elements before it that are smaller than itself
while len(self.maxq) > 0 and self.maxq[-1] < n:
self.maxq.pop()
self.maxq.append(n)
import (
"container/list"
)
type MonotonicQueue struct {
// use golang doubly linked list, supports adding and removing elements from head and tail
// maintain elements in increasing order from tail to head
maxq list.List
}
// add an element n to the tail, maintaining the monotonic property of mq
func (mq *MonotonicQueue) Push(n int) {
// remove all elements in front that are smaller than itself
for mq.maxq.Len() > 0 && mq.maxq.Back().Value.(int) < n {
mq.maxq.Remove(mq.maxq.Back())
}
}
class MonotonicQueue {
constructor() {
// JavaScript does not have a built-in data structure that
// supports fast addition and removal of elements from both ends
// Let's temporarily use a regular array, but this might
// perform poorly when removing elements from the head
// Maintain the elements in a monotonically increasing order from tail to head
this.maxq = []
}
// Add an element n to the tail, maintaining the monotonic property of maxq
push(n) {
// Remove all elements smaller than itself from the front
while (this.maxq.length > 0 && this.maxq[this.maxq.length - 1] < n) {
this.maxq.pop()
}
this.maxq.push(n)
}
}
Imagine that the size of a number represents a person's weight. A heavier weight will flatten the lighter ones in front of it until it encounters a weight of greater magnitude.

If each element is processed in this manner when added, the elements in the monotonic queue will maintain a monotonically decreasing order. This makes our max
method straightforward to implement: simply return the front element of the queue. The pop
method also operates on the front of the queue. If the front element is the element n
to be removed, then delete it:
class MonotonicQueue {
// to save space, the previous code section is omitted...
public int max() {
// the element at the front of the queue is definitely the largest
return maxq.getFirst();
}
public void pop(int n) {
if (n == maxq.getFirst()) {
maxq.pollFirst();
}
}
}
class MonotonicQueue {
// to save space, the code given above is omitted...
public:
int max() {
// the element at the front of the queue is definitely the largest
return maxq.front();
}
void pop(int n) {
if (n == maxq.front()) {
maxq.pop_front();
}
}
};
class MonotonicQueue:
# To save space, the previous code part is omitted...
def max(self) -> int:
# The element at the head of the queue is definitely the largest
return self.maxq[0]
def pop(self, n: int) -> None:
if n == self.maxq[0]:
self.maxq.popleft()
// to save space, the previous code part is omitted...
func (mq *MonotonicQueue) max() int {
// the front element of the queue is surely the largest
return mq.maxq.Front().Value.(int)
}
func (mq *MonotonicQueue) pop(n int) {
if n == mq.maxq.Front().Value.(int) {
mq.maxq.Remove(mq.maxq.Front())
}
}
class MonotonicQueue {
// in order to save space, the code above is omitted...
max() {
// the element at the head of the queue is definitely the largest
return this.maxq[0];
}
pop(n) {
if (n === this.maxq[0]) {
this.maxq.shift();
}
}
}
The reason the pop
method checks if n == maxq.getFirst()
is that the front element n
we want to remove might have been "flattened" during the push
process and may no longer exist. In this case, we don't need to remove it:

With this, the design of the monotonic queue is complete. Let's look at the full solution code:
class Solution {
// implementation of the monotonic queue
class MonotonicQueue {
LinkedList<Integer> q = new LinkedList<>();
public void push(int n) {
// remove all elements smaller than n
while (!q.isEmpty() && q.getLast() < n) {
q.pollLast();
}
// then add n to the end
q.addLast(n);
}
public int max() {
return q.getFirst();
}
public void pop(int n) {
if (n == q.getFirst()) {
q.pollFirst();
}
}
}
// implementation of the solution function
public int[] maxSlidingWindow(int[] nums, int k) {
MonotonicQueue window = new MonotonicQueue();
List<Integer> res = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
if (i < k - 1) {
// first fill the window with the first k - 1 elements
window.push(nums[i]);
} else {
// slide the window forward and add the new number
window.push(nums[i]);
// record the maximum value of the current window
res.add(window.max());
// remove the old number
window.pop(nums[i - k + 1]);
}
}
// need to convert to int[] array before returning
int[] arr = new int[res.size()];
for (int i = 0; i < res.size(); i++) {
arr[i] = res.get(i);
}
return arr;
}
}
// implementation of monotonic queue
class MonotonicQueue {
deque<int> maxq;
public:
void push(int n) {
// remove all elements smaller than n
while (!maxq.empty() && maxq.back() < n) {
maxq.pop_back();
}
// then add n to the back
maxq.push_back(n);
}
int max() {
return maxq.front();
}
void pop(int n) {
if (n == maxq.front()) {
maxq.pop_front();
}
}
};
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
MonotonicQueue window;
vector<int> res;
for (int i = 0; i < nums.size(); i++) {
if (i < k - 1) {
// first fill the window with the first k - 1 elements
window.push(nums[i]);
} else {
// slide the window forward and add a new number
window.push(nums[i]);
// record the max value of the current window
res.push_back(window.max());
// remove the old number
window.pop(nums[i - k + 1]);
}
}
return res;
}
};
class MonotonicQueue:
def __init__(self):
self.maxq = []
def push(self, n):
# remove all elements less than n
while self.maxq and self.maxq[-1] < n:
self.maxq.pop()
# then add n to the end
self.maxq.append(n)
def max(self):
return self.maxq[0]
def pop(self, n):
if n == self.maxq[0]:
self.maxq.pop(0)
class Solution(object):
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
window = MonotonicQueue()
res = []
for i in range(len(nums)):
if i < k - 1:
# first fill the window with the first k - 1 elements
window.push(nums[i])
else:
# slide the window forward, add new number
window.push(nums[i])
# record the maximum value of the current window
res.append(window.max())
# remove the old number
window.pop(nums[i - k + 1])
return res
import (
"container/list"
)
type MonotonicQueue struct {
maxq list.List
}
func (mq *MonotonicQueue) push(n int) {
// remove all elements smaller than n
for mq.maxq.Len() > 0 && mq.maxq.Back().Value.(int) < n {
mq.maxq.Remove(mq.maxq.Back())
}
// then add n to the back
mq.maxq.PushBack(n)
}
func (mq *MonotonicQueue) max() int {
return mq.maxq.Front().Value.(int)
}
func (mq *MonotonicQueue) pop(n int) {
if n == mq.maxq.Front().Value.(int) {
mq.maxq.Remove(mq.maxq.Front())
}
}
func maxSlidingWindow(nums []int, k int) []int {
window := MonotonicQueue{maxq: list.List{}}
res := []int{}
for i := 0; i < len(nums); i++ {
if i < k-1 {
// first fill the window with the first k - 1 elements
window.push(nums[i])
} else {
/* <extend up -100>
<div class="img-content"><img src="/images/monotonic-queue/1.png" alt class="myimage" loading="lazy" photo-swipe="" /></div>
*/
// slide the window forward, adding new number
window.push(nums[i])
// record the maximum value of the current window
res = append(res, window.max())
// remove the old number
window.pop(nums[i-k+1])
}
}
return res
}
// implementation of monotonic queue
class MonotonicQueue {
constructor() {
this.maxq = [];
}
push(n) {
// remove all elements smaller than n
while (this.maxq.length > 0 && this.maxq[this.maxq.length - 1] < n) {
this.maxq.pop();
}
// then add n to the back
this.maxq.push(n);
}
max() {
return this.maxq[0];
}
pop(n) {
if (n === this.maxq[0]) {
this.maxq.shift();
}
}
}
function maxSlidingWindow(nums, k) {
var window = new MonotonicQueue();
var res = [];
for (var i = 0; i < nums.length; i++) {
if (i < k - 1) {
// first fill the window with the first k - 1 elements
window.push(nums[i]);
} else {
// slide the window forward and add a new number
window.push(nums[i]);
// record the maximum value of the current window
res.push(window.max());
// remove the old number
window.pop(nums[i - k + 1]);
}
}
return res;
}
Do not overlook some detailed issues. When implementing MonotonicQueue
, we used Java's LinkedList
because the linked list structure supports fast insertion and deletion of elements at both the head and tail. Meanwhile, the res
in the solution code uses the ArrayList
structure, as elements will be accessed by index later, making the array structure more suitable. Pay attention to these details when implementing in other languages.
Regarding the time complexity of the monotonic queue API, readers might be puzzled: the push
operation contains a while loop, so the worst-case time complexity should be , and with an additional for loop, the algorithm's time complexity should be , right?
Here, we apply amortized analysis as mentioned in the Guide to Algorithm Time and Space Complexity Analysis:
Looking at the push
operation alone, the worst-case time complexity is indeed , but the average time complexity is . Typically, we use average complexity rather than the worst-case complexity to measure API interfaces, so the overall time complexity of this algorithm is , not .
Alternatively, analyzing from an overall perspective: the algorithm essentially involves adding and removing each element in nums
from the window
at most once. It is impossible to repeatedly add and remove the same element, so the overall time complexity is .
The space complexity is easy to analyze, which is the size of the window .
Further Exploration
Finally, I pose a few questions for you to consider:
The
MonotonicQueue
class provided in this article only implements themax
method. Can you add amin
method to return the minimum value of all elements in the queue in time?The
pop
method of theMonotonicQueue
class provided in this article still requires a parameter, which is not so elegant and goes against the standard queue API. Please fix this defect.Implement the
size
method of theMonotonicQueue
class to return the number of elements in the monotonic queue (note that eachpush
operation might remove elements from the underlyingq
list, so the number of elements inq
is not the number of elements in the monotonic queue).
In other words, can you implement a general-purpose monotonic queue:
// General implementation of a monotonic queue, which
// can efficiently maintain maximum and minimum values
class MonotonicQueue<E extends Comparable<E>> {
// Standard queue API to add an element to the back of the queue
public void push(E elem);
// Standard queue API to pop an element from the front of the queue, following FIFO order
public E pop();
// Standard queue API to return the number of elements in the queue
public int size();
// Monotonic queue specific API to compute the maximum value in the queue in O(1) time
public E max();
// Monotonic queue specific API to compute the minimum value in the queue in O(1) time
public E min();
}
// General implementation of a monotonic queue, which can
// efficiently maintain the maximum and minimum values
template <typename E>
class MonotonicQueue {
public:
// Standard queue API, add an element to the end of the queue
void push(E elem);
// Standard queue API, remove an element from the
// front of the queue, following the FIFO order
E pop();
// Standard queue API, return the number of elements in the queue
int size();
// Monotonic queue specific API, compute the maximum
// value among the elements in the queue in O(1) time
E max();
// Monotonic queue specific API, compute the minimum
// value among the elements in the queue in O(1) time
E min();
};
# General implementation of a monotonic queue, can
# efficiently maintain maximum and minimum values
class MonotonicQueue:
def push(self, elem: 'Comparable') -> None:
pass
# Standard queue API, pop elements from the front in FIFO order
def pop(self) -> 'Comparable':
pass
# Standard queue API, return the number of elements in the queue
def size(self) -> int:
pass
# Monotonic queue specific API, calculate the
# maximum value of elements in the queue in O(1) time
def max(self) -> 'Comparable':
pass
# Monotonic queue specific API, calculate the
# minimum value of elements in the queue in O(1) time
def min(self) -> 'Comparable':
pass
// MonotonicQueue is a general implementation of a monotonic
// queue that can efficiently maintain maximum and minimum values
type MonotonicQueue struct{}
type Comparable interface {
// compare function, the return value -1, 0, 1
// respectively represents less than, equal to, greater than
compare(Comparable) int
}
// push adds an element to the end of the queue
func (q *MonotonicQueue) push(elem Comparable) {}
// pop removes an element from the front of the queue, following the first-in-first-out order
func (q *MonotonicQueue) pop() Comparable {}
// size returns the number of elements in the queue
func (q *MonotonicQueue) size() int {}
// max is a specific API of the monotonic queue that
// calculates the maximum value of elements in O(1) time
func (q *MonotonicQueue) max() Comparable {}
// min is a specific API of the monotonic queue that
// calculates the minimum value of elements in O(1) time
func (q *MonotonicQueue) min() Comparable {}
// General implementation of a monotonic queue, can
// efficiently maintain the maximum and minimum values
class MonotonicQueue {
// Standard queue API, add elements to the end of the queue
push(elem) {}
// Standard queue API, remove elements from the front of the queue, following the FIFO order
pop() {}
// Standard queue API, return the number of elements in the queue
size() {}
// Monotonic queue specific API, calculate the
// maximum value of elements in the queue in O(1) time
max() {}
// Monotonic queue specific API, calculate the
// minimum value of elements in the queue in O(1) time
min() {}
}
I will provide a general implementation of the monotonic queue and classic exercises in General Implementation and Applications of Monotonic Queue. For more data structure design problems, see Classic Exercises on Data Structure Design.
Related Problems
You can install my Chrome extension then open the link.
LeetCode | Difficulty |
---|---|
1425. Constrained Subsequence Sum | 🔴 |
1696. Jump Game VI | 🟠 |
862. Shortest Subarray with Sum at Least K | 🔴 |
918. Maximum Sum Circular Subarray | 🟠 |