The previous article talked about a special data structure called “monotonic stack”, which solved a type of problem called “Next Greater Number”. This article will write a similar data structure called “monotonic queue”.
Maybe you haven’t heard of this data structure before. It’s actually not that difficult. It’s just a “queue”. It just uses a little trick to make the elements in the queue monotonically increase (or decrease). What is this data structure used for? It can solve a series of problems of sliding windows.
PS: I have written more than 100 original articles and practiced 200 Likou questions. All of them are published in labuladong’s algorithm cheat sheet and are continuously updated . It is recommended to collect them and practice questions in the order of my articles . After mastering various algorithm routines, you will feel at ease when you enter the sea of questions.
Look at a LeetCode question, the difficulty is hard:
1. Build a problem-solving framework
This problem is not complicated. The difficulty lies in how to calculate the maximum value in each “window” in O(1) time so that the entire algorithm can be completed in linear time. We have discussed similar scenarios before and came to a conclusion:
If the maximum value of a group of numbers is known and a number is added to the group, the maximum value can be quickly calculated by comparison. However, if a number is reduced, the maximum value may not be obtained quickly and it is necessary to traverse all numbers and find the maximum value again.
Back to the scenario of this question, when each window moves forward, a number needs to be added and a number reduced at the same time. Therefore, if you want to get the new maximum value in O(1) time, you need a special data structure such as “monotonic queue” to assist.
A normal queue must have these two operations
Of course, the implementation methods of these APIs are definitely different from those of general Queues, but let’s ignore that for now and assume that the time complexity of these operations is O(1). Let’s first build a framework for solving this “sliding window” problem:
This idea is very simple, do you understand it? Now let’s start the main part, the implementation of monotonic queue.
2. Implementing Monotonic Queue Data Structure
First we need to know another data structure: deque, or double-ended queue. It’s very simple:
Moreover, the complexity of these operations is O(1). This is actually not a rare data structure. If a linked list is used as the underlying structure, it is easy to implement these functions.
The core idea of ”monotonic queue” is similar to that of “monotonic stack”. The push method of monotonic queue still adds elements to the end of the queue, but deletes all the elements smaller than the new element:
You can imagine that the size of the added numbers represents the weight of a person, which crushes those who are underweight until they reach a larger magnitude.
PS: I have written more than 100 original articles and practiced 200 Likou questions. All of them are published in labuladong’s algorithm cheat sheet and are continuously updated . It is recommended to collect them and practice questions in the order of my articles . After mastering various algorithm routines, you will feel at ease when you enter the sea of questions.
Hurry up and solve LeetCode question 239~
If this operation is performed when each element is added, the size of the elements in the final monotonic queue will remain in a monotonically decreasing order, so our max() API can be written like this.
The reason for this is that the head element n that we want to delete may have been “flattened”, so we don’t need to delete it at this time:
At this point, the monotonic queue design is complete. Let’s take a look at the complete problem-solving code:
3. Algorithm Complexity Analysis
Readers may wonder, since the push operation ome of these forms are contains a while loop, the time complexity is not O(1), so the time complexity of this algorithm should not be linear time, right?
The complexity of the push operation alone is indeed not O(1), but the complexity of the algorithm as a whole is still O(N) linear time. Think of it this way: each element in nums is pushed_back and pop_back at most once, without any redundant operations, so the overall complexity is still O(N).
The space complexity is very simple, it is the size of the window O(k).
4. Final summary
Some readers may think that “monotonic queue” and “priority queue” are similar, but in fact they are very different.
A monotonic queue maintains the monotonicity big work of the queue by deleting elements when adding them, which is equivalent to extracting the monotonically increasing (or decreasing) part of a function; while a priority queue (binary heap) is equivalent to automatic sorting, which is a huge difference.
My online e-book has 100 original articles and guides you through 200 puzzles. I recommend saving it! The corresponding GitHub algorithm repository has received 70k stars. You are welcome to star it!