博客

1 什么是单调队列

顾名思义，单调队列原则上也是一种

队列

，只不过在队列的基础上，有一些额外的功能是基本的队列所没有的。比如说每次出队的元素都比上一次的元素大或者小，这就是一种单调队列。

2 Java代码实现

import java.util.Deque;
import java.util.LinkedList;

/**
 * 单调队列
 */
public class SingleQueue {
    private Deque<Integer> deque = new LinkedList<>();

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

    public int peek(){
        if (this.deque.isEmpty())
            return -1;
        return this.deque.getFirst();
    }


    public static void main(String[] args) {
        SingleQueue singleQueue = new SingleQueue();
        singleQueue.push(1);
        singleQueue.push(3);
        singleQueue.push(1);
        singleQueue.push(2);
        singleQueue.push(0);
        singleQueue.push(5);
        System.out.println(singleQueue.peek());

    }

}