Exercise: Monotonic Queue Implementation and Leetcode Problems
Prerequisite Knowledge
Before reading this article, you need to be familiar with:
General Implementation
I will first provide a general implementation of the monotonic queue structure. This involves the use of Java generics, where E represents any type. E extends Comparable<E> means that the type E must implement the Comparable interface, indicating that the type E is comparable, such as Integer, String, which implement the compareTo method. The reason for this is quite simple: since you're asking for the maximum or minimum value in the queue, the elements must be comparable (i.e., have a defined order).
Our original simplistic implementation included the implementation of the max method, whose principle is to maintain a queue maxq that keeps the elements from the tail to the head in a monotonically increasing order.