Introduction to Monotonic Queues – GeeksforGeeks

By Ann Roberts On Jan 19, 2023

Improve Article

Save Article

Like Article

Improve Article

Save Article

A monotonic queue is a data structure that supports efficient insertion, deletion, and retrieval of elements in a specific order, typically in increasing or decreasing order.

The monotonic queue can be implemented using different data structures, such as a linked list, stack, or deque. The most common implementation is using a deque (double-ended queue) container. The deque container allows efficient insertion and deletion of elements from both the front and back of the queue, which is useful for implementing a monotonic queue.

There are two main types of monotonic queues:

Increasing Monotonic Queue: It only keeps elements in increasing order, and any element that is smaller than the current minimum is removed.
Decreasing Monotonic Queue: It only keeps elements in decreasing order, and any element that is larger than the current maximum is removed.

Implement the idea below to solve the Increasing Monotonic Queue problem:

The function starts by initializing an empty deque called q.
Then, it loops through the input array. For each element in the array, it checks if the deque is not empty and if the last element in the deque is greater than the current element in the array.
If this condition is true, the last element in the deque is popped out. This is because we only want to keep elements in increasing order and any element that is smaller than the current minimum is removed.
After that, the current element in the array is pushed into the deque.
This process is repeated for all elements in the input array
At the end of the function, the deque containing the increasing monotonic queue is returned.

Here’s an example of an increasing monotonic queue implemented in C++:

C++

#include <bits/stdc++.h>

using namespace std;

deque<int> increasing_monotonic_queue(int arr[], int n)

{

deque<int> q;

for (int i = 0; i < n; i++) {

while (!q.empty() && q.back() > arr[i]) {

q.pop_back();

}

q.push_back(arr[i]);

}

return q;

}

int main()

{

int arr[] = { 1, 2, 3, 4, 5, 6 };

int n = sizeof(arr) / sizeof(arr[0]);

deque<int> q = increasing_monotonic_queue(arr, n);

for (int i : q) {

cout << i << " ";

}

return 0;

}

Implement the idea below to solve the Decreasing Monotonic Queue problem:

The function starts by initializing an empty deque called q.
Then, it loops through the input array. For each element in the array, it checks if the deque is not empty and if the last element in the deque is smaller than the current element in the array.
If this condition is true, the last element in the deque is popped out. This is because we only want to keep elements in decreasing order and any element that is larger than the current maximum is removed.
After that, the current element in the array is pushed into the deque.
This process is repeated for all elements in the input array
At the end of the function, the deque containing the decreasing monotonic queue is returned.

Here is an example of a decreasing monotonic queue implemented in C++:

C++

#include <deque>

#include <iostream>

using namespace std;

deque<int> decreasing_monotonic_queue(int arr[], int n)

{

deque<int> q;

for (int i = 0; i < n; i++) {

while (!q.empty() && q.back() < arr[i]) {

q.pop_back();

}

q.push_back(arr[i]);

}

return q;

}

int main()

{

int arr[] = { 6, 5, 4, 3, 2, 1 };

int n = sizeof(arr) / sizeof(arr[0]);

deque<int> q = decreasing_monotonic_queue(arr, n);

for (int i : q) {

cout << i << " ";

}

return 0;

}

Applications of monotonic queue include:

Finding the maximum or minimum element in a sliding window
Solving dynamic programming problems such as LIS (longest increasing subsequence) and LDS (longest decreasing subsequence)

Advantages of the monotonic queue:

It is efficient in terms of both time and space complexity.
It is easy to implement.

Disadvantages of the monotonic queue:

It is not suitable for all types of problems, only those that involve finding the maximum or minimum element in a specific order
It has limited functionality compared to more advanced data structures such as segment trees and Fenwick trees.

Improve Article

Save Article

Like Article

Improve Article

Save Article

A monotonic queue is a data structure that supports efficient insertion, deletion, and retrieval of elements in a specific order, typically in increasing or decreasing order.

There are two main types of monotonic queues:

Increasing Monotonic Queue: It only keeps elements in increasing order, and any element that is smaller than the current minimum is removed.
Decreasing Monotonic Queue: It only keeps elements in decreasing order, and any element that is larger than the current maximum is removed.

Implement the idea below to solve the Increasing Monotonic Queue problem:

The function starts by initializing an empty deque called q.
Then, it loops through the input array. For each element in the array, it checks if the deque is not empty and if the last element in the deque is greater than the current element in the array.
If this condition is true, the last element in the deque is popped out. This is because we only want to keep elements in increasing order and any element that is smaller than the current minimum is removed.
After that, the current element in the array is pushed into the deque.
This process is repeated for all elements in the input array
At the end of the function, the deque containing the increasing monotonic queue is returned.

Here’s an example of an increasing monotonic queue implemented in C++:

C++

#include <bits/stdc++.h>

using namespace std;

deque<int> increasing_monotonic_queue(int arr[], int n)

{

deque<int> q;

for (int i = 0; i < n; i++) {

while (!q.empty() && q.back() > arr[i]) {

q.pop_back();

}

q.push_back(arr[i]);

}

return q;

}

int main()

{

int arr[] = { 1, 2, 3, 4, 5, 6 };

int n = sizeof(arr) / sizeof(arr[0]);

deque<int> q = increasing_monotonic_queue(arr, n);

for (int i : q) {

cout << i << " ";

}

return 0;

}

Implement the idea below to solve the Decreasing Monotonic Queue problem:

The function starts by initializing an empty deque called q.
Then, it loops through the input array. For each element in the array, it checks if the deque is not empty and if the last element in the deque is smaller than the current element in the array.
If this condition is true, the last element in the deque is popped out. This is because we only want to keep elements in decreasing order and any element that is larger than the current maximum is removed.
After that, the current element in the array is pushed into the deque.
This process is repeated for all elements in the input array
At the end of the function, the deque containing the decreasing monotonic queue is returned.

Here is an example of a decreasing monotonic queue implemented in C++:

C++

#include <deque>

#include <iostream>

using namespace std;

deque<int> decreasing_monotonic_queue(int arr[], int n)

{

deque<int> q;

for (int i = 0; i < n; i++) {

while (!q.empty() && q.back() < arr[i]) {

q.pop_back();

}

q.push_back(arr[i]);

}

return q;

}

int main()

{

int arr[] = { 6, 5, 4, 3, 2, 1 };

int n = sizeof(arr) / sizeof(arr[0]);

deque<int> q = decreasing_monotonic_queue(arr, n);

for (int i : q) {

cout << i << " ";

}

return 0;

}

Applications of monotonic queue include:

Finding the maximum or minimum element in a sliding window
Solving dynamic programming problems such as LIS (longest increasing subsequence) and LDS (longest decreasing subsequence)

Advantages of the monotonic queue:

It is efficient in terms of both time and space complexity.
It is easy to implement.

Disadvantages of the monotonic queue:

It is not suitable for all types of problems, only those that involve finding the maximum or minimum element in a specific order
It has limited functionality compared to more advanced data structures such as segment trees and Fenwick trees.

Read original article here

Denial of responsibility! Techno Blender is an automatic aggregator of the all world’s media. In each content, the hyperlink to the primary source is specified. All trademarks belong to their rightful owners, all materials to their authors. If you are the owner of the content and do not want us to publish your materials, please contact us by email – [email protected]. The content will be deleted within 24 hours.