A monotonic queue is a specialized data structure that maintains elements in a specific order—either increasing or decreasing—as they are processed. Unlike a regular queue, where the order of elements strictly follows the sequence of insertion, a monotonic queue ensures that the elements are arranged in a way that optimizes certain operations, such as finding the minimum or maximum in a sliding window.

The monotonic queue pattern is crucial in solving problems where you need to efficiently manage a sliding window over a list of elements. It allows you to maintain order such that finding the minimum or maximum element within the current window becomes an O(1) operation. This efficiency is especially useful in scenarios involving large datasets where brute-force methods would be too slow.

Implementation of Monotonic Increasing Queue

A monotonic queue is typically implemented using a deque (double-ended queue). The deque is chosen because it allows efficient addition and removal of elements from both ends, which is crucial in maintaining the order of elements as new ones are processed.

In the case of a monotonic increasing queue, the elements are maintained in non-decreasing order. This structure is particularly useful for solving problems that require tracking the minimum value within a dynamic range, such as in sliding window problems.

Step-by-Step Algorithm

1. Initialize an empty deque to store the indices of elements (or the elements themselves, depending on the problem).
2. Iterate through each element in the array or list.
3. Maintain Order:
   • While the deque is not empty and the current element is smaller than or equal to the element at the back of the deque, remove the back element. This ensures that the deque remains in increasing order.
4. Add Current Element:
   • Append the current element (or its index) to the back of the deque.
5. Continue to the next element and repeat the process until all elements have been processed.
6. Return the Queue.

Algorithm Walkthrough

Let's walk through the code step by step with the example array nums = {7, 5, 6, 4, 8} to see how the monotonic increasing queue is built:

1. Initialization:

   • An empty deque deque is created to store elements while maintaining the monotonic increasing order.

2. Iteration:

   • The algorithm iterates through each element in the array nums.

3. Processing 7 (First Element):

   • The deque is empty, so 7 is added directly.
   • Deque State: [7]

4. Processing 5 (Second Element):

   • 5 is less than 7, so 7 is removed from the deque to maintain the increasing order.
   • 5 is then added to the deque.
   • Deque State: [5]

5. Processing 6 (Third Element):

   • 6 is greater than 5, so it is added directly to the deque.
   • Deque State: [5, 6]

6. Processing 4 (Fourth Element):

   • 4 is less than 6 and 5, so both 6 and 5 are removed from the deque.
   • 4 is then added to the deque.
   • Deque State: [4]

7. Processing 8 (Fifth Element):

   • 8 is greater than 4, so it is added directly to the deque.
   • Deque State: [4, 8]

8. Final Output:

   • After processing all elements, the final monotonic increasing queue in the deque is [4, 8].

Code

Complexity Analysis

• Time Complexity: O(n). Each element is added and removed from the deque at most once, leading to a linear time complexity.

• Space Complexity: O(n). In the worst case, the deque can hold up to n elements if the array is strictly increasing or decreasing.

Implementation of Monotonic Decreasing Queue

In the case of a monotonic decreasing queue, the elements are maintained in non-increasing order. This structure is particularly useful for solving problems that require tracking the maximum value within a dynamic range, such as in sliding window problems.

Step-by-Step Algorithm

1. Initialize an empty deque to store the indices of elements (or the elements themselves, depending on the problem).
2. Iterate through each element in the array or list.
3. Maintain Order:
   • While the deque is not empty and the current element is greater than or equal to the element at the back of the deque, remove the back element. This ensures that the deque remains in decreasing order.
4. Add Current Element:
   • Append the current element (or its index) to the back of the deque.
5. Continue to the next element and repeat the process until all elements have been processed.
6. Return the Queue.

Algorithm Walkthrough

Let's walk through the code step by step with the example array nums = {7, 5, 6, 4, 8} to see how the monotonic decreasing queue is built:

1. Initialization:

   • An empty deque deque is created to store elements while maintaining the monotonic decreasing order.

2. Iteration:

   • The algorithm iterates through each element in the array nums.

3. Processing 7 (First Element):

   • The deque is empty, so 7 is added directly.
   • Deque State: [7]

4. Processing 5 (Second Element):

   • 5 is less than 7, so 5 is added directly to the deque.
   • Deque State: [7, 5]

5. Processing 6 (Third Element):

   • 6 is greater than 5, so 5 is removed from the deque to maintain the decreasing order.
   • 6 is then added to the deque.
   • Deque State: [7, 6]

6. Processing 4 (Fourth Element):

   • 4 is less than 6, so it is added directly to the deque.
   • Deque State: [7, 6, 4]

7. Processing 8 (Fifth Element):

   • 8 is greater than all the elements in the deque, so 4, 6, and 7 are removed from the deque.
   • 8 is then added to the deque.
   • Deque State: [8]

8. Final Output:

   • After processing all elements, the final monotonic decreasing queue in the deque is [8].

Code

Complexity Analysis

• Time Complexity: O(n). Each element is added and removed from the deque at most once, leading to a linear time complexity.

• Space Complexity: O(n). In the worst case, the deque can hold up to n elements if the array is strictly increasing or decreasing.

Common Use Cases

• Sliding Window Problems: Used to find the maximum or minimum value in a sliding window, such as the "Sliding Window Maximum" problem.
• Range Queries: Quickly queries the minimum or maximum value in a dynamic range.
• Optimization Problems: Helps in maintaining optimal values efficiently for operations like minimizing cost or maximizing profit.

Now, let's start solving problems on Monotonic Queue.