Monotonic Decreasing Queue

A monotonic decreasing deque is a double-ended queue where elements are in non-increasing order from front to back. Elements can be efficiently inserted and removed while maintaining order.

Java example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class MonotonicQueue {
  
  Deque<Integer> q = new LinkedList();

  void push(int n) {
    while (!q.isEmpty() && q.peekLast() < n) {
      q.removeLast();
    }
    q.addLast(n);
  }

  int max() {
    return q.peekFirst(); 
  }

  void pop(int n) {
    if (!q.isEmpty() && n == q.peekFirst()) {
      q.removeFirst();
    }
  }
}

C++ example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class MonotonicQueue {
  deque<int> q; 

public:
  void push(int n) {
    while (!q.empty() && q.back() < n) {
      q.pop_back();
    }
    q.push_back(n);
  }

  int max() {
    return q.front();
  }

  void pop(int n) {
    if (!q.empty() && n == q.front()) {
      q.pop_front(); 
    }
  }
};

Python example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
from collections import deque

class MonotonicQueue:

  def __init__(self):
    self.q = deque()

  def push(self, n):
    while self.q and self.q[-1] < n:
      self.q.pop()
    self.q.append(n)

  def max(self):
    return self.q[0]  

  def pop(self, n):
    if self.q and n == self.q[0]:
      self.q.popleft()

Monotonic dequeues provide efficient insert and delete from both ends while maintaining sorted order.

A monotonic decreasing queue is a data structure that maintains elements in a decreasing order. Elements can be added to the queue, and when a new element is inserted, all elements that are less than the new element are removed from the back of the queue. This ensures that the elements in the queue are always in a decreasing order. The front element of the queue is always the maximum value of the current window or subarray. Monotonic decreasing queues are often used in algorithms that require sliding window operations, finding maximum elements in subarrays, etc.

Solution

Java

Here’s how you can implement a monotonic decreasing queue in Java using a Deque:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.Deque;
import java.util.LinkedList;

public class MonotonicDecreasingQueue {
    Deque<Integer> deque = new LinkedList<>();

    public void push(int value) {
        while (!deque.isEmpty() && deque.getLast() < value) {
            deque.removeLast();
        }
        deque.addLast(value);
    }

    public int max() {
        return deque.getFirst();
    }

    public void pop(int value) {
        if (!deque.isEmpty() && deque.getFirst() == value) {
            deque.removeFirst();
        }
    }
}

C++

Implementing a monotonic decreasing queue using C++:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <deque>

class MonotonicDecreasingQueue {
    std::deque<int> deque;

public:
    void push(int value) {
        while (!deque.empty() && deque.back() < value) {
            deque.pop_back();
        }
        deque.push_back(value);
    }

    int max() {
        return deque.front();
    }

    void pop(int value) {
        if (!deque.empty() && deque.front() == value) {
            deque.pop_front();
        }
    }
};

Python

Here’s a Python implementation of a monotonic decreasing queue using collections.deque:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
from collections import deque

class MonotonicDecreasingQueue:
    def __init__(self):
        self.deque = deque()

    def push(self, value):
        while self.deque and self.deque[-1] < value:
            self.deque.pop()
        self.deque.append(value)

    def max(self):
        return self.deque[0]

    def pop(self, value):
        if self.deque and self.deque[0] == value:
            self.deque.popleft()

In these implementations, the push method ensures that the elements in the queue are in a decreasing order by removing elements from the back that are less than the new element. The max method returns the current maximum element, and the pop method can be used to remove an element from the front if it matches the specified value.