Monotonic Queue to Solve Sliding Window Problems

In a previous article, Solving Three Algorithm Problems with Monotonic Stack, we introduced the special data structure called the monotonic stack. In this article, we will discuss a similar data structure called the "monotonic queue."

You may not have heard of this data structure before, but it's not complicated. It is essentially a "queue" that uses a clever method to ensure that all elements in the queue are either 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 extremum value A, if you add a number B to window, you can immediately calculate the new extremum by comparing A and B. However, if you remove a number from the window array, you cannot directly obtain the extremum, because if the removed number happens to be A, you would need to traverse all elements in window to find the new extremum.

This scenario is quite common, but it seems that you do not necessarily need a monotonic queue to solve it. For example, a priority queue (binary heap) is designed for dynamically finding extrema. By creating a max (min) heap, you can quickly get the maximum (minimum) value.

While a priority queue is professional for maintaining extrema since the head of the queue is the extremum, it cannot satisfy the standard queue structure's "first-in-first-out" time order. This is because the priority queue uses a binary heap to dynamically sort elements, and the order of dequeue follows the size of elements, not their enqueue order.

Therefore, we need a new queue structure that can maintain both the "first-in-first-out" time order of elements and the correct extrema of all elements in the queue. This is the "monotonic queue" structure.

The "monotonic queue" is primarily used to help solve problems related to sliding windows. In a previous article, Core Framework of Sliding Windows, the sliding window algorithm was discussed as part of the two-pointer technique. However, slightly more complex sliding window problems cannot be solved by just two pointers; they require more advanced data structures.

For instance, if you look at the problems discussed in the previous article Core Framework of Sliding Windows, each time the window expands (right++) or shrinks (left++), you can decide whether to update the solution based solely on the elements entering or leaving the window.

However, in the example mentioned at the beginning of this article about determining the extremum of a window, you cannot update the window's extremum based solely on the element leaving the window unless you traverse all elements again, which increases the time complexity—something we want to avoid.

Let's consider LeetCode problem 239, "Sliding Window Maximum," which is a standard problem involving sliding windows:

You are given an input array nums and a positive integer k. There is a window of size k that slides from left to right across nums. You need to output the maximum value of the k elements in the window each time it moves.

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)

比如说力扣给出的一个示例：

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置                最大值
---------------               -----
[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 $O(1)$ 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 a 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 few APIs for a monotonic queue is definitely different from a regular Queue. But for now, let's not worry about that and assume that the time complexity for these operations is O(1). Let's first establish the framework for solving 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 simple, right? Now let's get to the main part, implementing the monotonic queue.

2. Implementing the Monotonic Queue Data Structure

By observing the sliding window process, you will find that to implement a "monotonic queue," we need a data structure that allows 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 to the tail of the queue, but it removes all elements in front that are smaller than the new element:

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
        // Let's temporarily use a regular array, but this
        // might perform poorly when removing elements from
        // 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:

// Implementation of a monotonic queue
class MonotonicQueue {
    LinkedList<Integer> maxq = new LinkedList<>();
    public void push(int n) {
        // remove all elements less than n
        while (!maxq.isEmpty() && maxq.getLast() < n) {

            maxq.pollLast();
        }
        // then add n to the end
        maxq.addLast(n);
    }
    
    public int max() {
        return maxq.getFirst();
    }
    
    public void pop(int n) {
        if (n == maxq.getFirst()) {
            maxq.pollFirst();
        }
    }
}

class Solution {
    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 a 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 an 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;
}

There is a minor detail that should not be overlooked. When implementing MonotonicQueue, we used Java's LinkedList because this structure supports fast addition and removal of elements at both the head and tail. Meanwhile, in the solution code, res uses the ArrayList structure, as it is more suitable for element access by index. Implementations in other languages should also pay attention to these details.

Regarding the time complexity of the monotonic queue API, readers might have some doubts: The push operation contains a while loop, so in the worst case, the time complexity should be $O(N)$. Adding a for loop on top of that, shouldn't the overall time complexity of this algorithm be $O(N^2)$?

This is where Guide to Time and Space Complexity Analysis comes into play, particularly the amortized analysis:

When you look at the push operation alone, the worst-case time complexity is indeed $O(N)$, but the average time complexity is $O(1)$. We generally use average complexity rather than worst-case complexity to measure API interfaces, so the overall time complexity of this algorithm is $O(N)$, not $O(N^2)$.

You can also analyze it from an overall perspective: The algorithm involves adding and removing each element in nums from window at most once. It is not possible to move the same element in and out of window multiple times, so the overall time complexity is $O(N)$.

The space complexity is easy to analyze, which is the size of the window, $O(k)$.

Further Exploration

Finally, I present a few questions for you to consider:

1. The MonotonicQueue class provided in this article only implements the max method. Can you add a min method that returns the minimum value of all elements in the queue in $O(1)$ time?

2. The pop method of the MonotonicQueue class requires an additional parameter, which is not very elegant and contradicts the standard queue API. Please address this issue.

3. Implement the size method for the MonotonicQueue class to return the number of elements in the monotonic queue. Note that the number of elements in the underlying q list may not reflect the actual number of elements in the monotonic queue due to potential deletions during each push operation.

In other words, can you implement a general version of the 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
    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)
    def max(self) -> 'Comparable':
        pass
    
    # Monotonic queue specific API, calculate the
    # minimum value of elements in the queue in O(1)
    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,
    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)
    max() {}

    // Monotonic queue specific API, calculate the
    // minimum value of elements in the queue in O(1)
    min() {}
}

I will provide a generic implementation and classic exercises for monotonic queues in Generic Implementation and Applications of Monotonic Queues. For more data structure design problems, refer to Classic Exercises on Data Structure Design.