1.基本概述
单调队列就是队列中的元素按照一定的单调性排列，通常是单调递增或单调递减。单调队列常用于解决一些需要维护一定顺序性的问题，例如滑动窗口最大值问题、动态规划问题等。在实现单调队列时，通常会利用双端队列（deque）来实现，因为双端队列支持在队首和队尾进行高效的插入和删除操作。通过在队列中维护单调性，可以使得在队列中进行查询操作时的复杂度保持在较低水平。
与普通队列不同的是，单调队列中存储的是元素的索引，而不是元素本身。这样做的好处是可以在队列中记录元素的位置信息，方便在需要时进行索引操作。
在滑动窗口问题中，单调队列通常用来解决在一个固定大小的窗口内找到最大值或最小值的问题。
比如在在滑动窗口问题中单调队列的维护过程：
- 入队操作： 每当有新的元素要入队时，首先要保证队列的单调性。如果新元素比队尾元素满足的单调性条件更好（比如更大或更小），则将队尾元素出队，直到队列为空或者新元素满足队尾元素的单调性条件。然后将新元素入队。
- 出队操作： 在滑动窗口的过程中，当窗口移动时，可能需要将队列中超出窗口范围的元素出队。在出队时，需要检查队首元素的索引是否在当前窗口的范围内，如果不在，则将其出队，直到队首元素的索引在窗口范围内为止。
- 获取队首元素： 队首元素始终是当前窗口的最大值或最小值所在的位置。因此，需要通过队首元素的索引来获取对应的元素值。
为什么单调队列能解决滑动窗口问题？
通过维护单调队列的性质，可以在每个窗口中快速地获取最大值或最小值。在滑动窗口向右移动时，通过入队和出队操作，保证了队列中的元素仍然是当前窗口内的元素，并且保持了单调性。这样，只需获取队首元素的值即可得到当前窗口的最大值或最小值。
2.滑动窗口最大值
可以使用优先队列（堆），不过还有一种更效率高的做法。
就是使用单调队列。
代码：
package com.dreams.data;
import java.util.Deque;
import java.util.LinkedList;
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
Deque<Integer> deque = new LinkedList<Integer>();
for (int i = 0; i < k; ++i) {
while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
deque.pollLast();
}
deque.offerLast(i);
}
int[] ans = new int[n - k + 1];
ans[0] = nums[deque.peekFirst()];
for (int i = k; i < n; ++i) {
while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
deque.pollLast();
}
deque.offerLast(i);
//检查队首元素是否在当前窗口范围内
while (deque.peekFirst() <= i - k) {
deque.pollFirst();
}
ans[i - k + 1] = nums[deque.peekFirst()];
}
return ans;
}
}首先创建了一个双端队列 deque，用于存储元素的索引。在循环遍历数组 nums 的前 k 个元素时，通过维护 deque 中的单调递减性质，保证了队列中的索引对应的元素值是递减的。这样，队列中的第一个元素始终是当前滑动窗口的最大值对应的索引。
然后，在遍历剩余的数组元素时，依次加入新的元素到 deque 中，并且保持队列中的索引对应的元素值递减的性质。同时，通过检查队首元素是否在当前窗口范围内，来维护窗口的大小。最后，将每个窗口的最大值存储到结果数组 ans 中并返回。
参考
