【强化练习】单调队列的通用实现及经典习题
Prerequisites
Before reading this article, you should learn:
General Implementation
First, I'll provide a general implementation of a monotonic queue structure. This involves Java generics, where E represents any type. The Java Language Basics at the beginning of this site covers this, so I won't go into detail here.
E extends Comparable<E> means that the type E must implement the Comparable interface, i.e., type E is comparable, such as types like Integer, String that implement the compareTo method. The reason is straightforward: you need to find the maximum or minimum value in the queue, so the elements must be comparable.
Our original simple implementation included the max method, which works by maintaining a queue maxq at the backend. This queue ensures that elements from the tail to the head are monotonically increasing.