前言1 单调栈2 单调队列参考
前言为什么写这篇文章呢？是因为笔者今天在写单调队列题目239. Sliding Window Maximum时，发现使用双端队列的时效性有点差强人意，所以尝试利用数组来模拟单调队列从而提升代码的运行效率。
1 单调栈待续。。。。。。
2 单调队列讲解单调队列之前，先简单介绍下什么是队列，以及什么是单调队列，特别地，用 Java 的同学肯定还知道优先级队列：
队列：队列是一种先进先出的数据结构，一般是从队列尾部入队，从队列头部出队，非常像我们日常打饭、买火车票时排列的队伍（插队的情况除外～）单调队列：即单调递减或单调递增的队列。使用频率不高，但在有些程序中会有非同寻常的作用。（摘自百度，使用频率不高扎心了）优先级队列：也即堆这种数据结构，特点是队首是具有最高优先级的元素（这里的最高优先级通常是指最大或者最小）。注意优先级队列与单调队列的区别：优先级队列只保证队首为最值，或者父子间有一定的大小关系，但是整个队列不保证是单调有序的；而单调队列保证整个队列是单调递增或单调递减的。
了解了单调队列的定义，下面我们就以一到实际的题目来看看如何应用吧。
题目链接：239. Sliding Window Maximum
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置 最大值
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
示例 2：
输入：nums = [1], k = 1
输出：[1]
示例 3：
输入：nums = [1,-1], k = 1
输出：[1,-1]
示例 4：
输入：nums = [9,11], k = 2
输出：[11]
思路：（优先级队列）本题题目名称中虽然待有“滑动窗口”的字样，但是本题却不是用滑动窗口来解的。首先我们可以用暴力解法：每滑动到一个新的窗口，我们都用 O(k) 的时间复杂度去遍历当前窗口的所有值从而获得最大值。但是这样势必效率较低，因为窗口每次滑动一位，也就意味着仅有一个元素加入队尾并且仅有一个元素从队首移除，如果每一次都在仅有两个元素变动的情况下去遍历整个 k 范围的数组去寻找最值，有点过于奢侈了。如果我们仅比较新加入的元素与原来窗口的最大值，就能得到当前窗口的最大值。自然而然，我们想到使用优先级队列这种数据结构，每次都能在 O(1) 时间复杂度内获得出口内的最大值，但是这样又会引发另外一个问题：由于窗口是从左往右滑动的，我们现在是可以利用优先级队列在 O(1) 时间复杂度内获得出口内的最大值，但是如果这个最大值滑出当前窗口了怎么办？很多同学想当然地认为将其从优先级队列的队首移出即可，但是仔细想想，这样真的准确吗？如果仅仅是简单地将不在窗口内的最大值移除，那你一定能保证移除后新的队首元素（新的最大值）也一定在窗口范围内吗？所以我们需要利用一个循环，只要当前的队首（最大值）不在窗口内，就将其移除，这样我们就能保证每次获取到的最大值都是在窗口内的有效最大值。
- 方法一：暴力法
思路：（优先级队列）本题题目名称中虽然待有“滑动窗口”的字样，但是本题却不是用滑动窗口来解的。首先我们可以用暴力解法：每滑动到一个新的窗口，我们都用 O(k) 的时间复杂度去遍历当前窗口的所有值从而获得最大值。但是这样势必效率较低，因为窗口每次滑动一位，也就意味着仅有一个元素加入队尾并且仅有一个元素从队首移除，如果每一次都在仅有两个元素变动的情况下去遍历整个 k 范围的数组去寻找最值，有点过于奢侈了。代码：
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
// 暴力解法
if (nums == null || nums.length < 1 || k < 1) {
throw new IllegalArgumentException();
}
int length = nums.length;
int[] res = new int[length - k + 1];
// i 为窗口的左边界
for (int i = 0; i < length - k + 1; i++) {
int max = Integer.MIN_VALUE;
// j 从左边界开始，滑过窗口的范围
for (int j = i; j < i + k; j++) {
max = Math.max(max, nums[j]); // 记录窗口内的最大值
}
res[i] = max;
}
return res;
}
}
时间复杂度 : O(nk) 不出所料，超时。。。空间复杂度: O(1)
- 方法二：优先级队列
思路：方法一需要每次都比较 k 个元素，有点浪费时间，如果我们仅比较新加入的元素与原来窗口的最大值，就能得到当前窗口的最大值。自然而然，我们想到使用优先级队列这种数据结构，每次都能在 O(1) 时间复杂度内获得出口内的最大值，但是这样又会引发另外一个问题：由于窗口是从左往右滑动的，我们现在是可以利用优先级队列在 O(1) 时间复杂度内获得出口内的最大值，但是如果这个最大值滑出当前窗口了怎么办？很多同学想当然地认为将其从优先级队列的队首移出即可，但是仔细想想，这样真的准确吗？如果仅仅是简单地将不在窗口内的最大值移除，那你一定能保证移除后新的队首元素（新的最大值）也一定在窗口范围内吗？所以我们需要利用一个循环，只要当前的队首（最大值）不在窗口内，就将其移除，这样我们就能保证每次获取到的最大值都是在窗口内的有效最大值。代码
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
// 优先级队列：先将当前元素的下标加入队列（队列按照值从大到小排序下标），在记录最大值之前需要先判断当前队列头是否还在窗口范围内
if (nums == null || nums.length < 1 || k < 1) {
throw new IllegalArgumentException();
}
int length = nums.length;
int[] res = new int[length - k + 1];
// 优先级队列（大根堆），存储的是元素下标，按照元素大小从大到小排列
PriorityQueue pq = new PriorityQueue<>((o1, o2) -> nums[o2] - nums[o1]);
for (int i = 0; i < length; i++) {
pq.offer(i);
// 窗口的左边界
int left = i - k + 1;
// 如果队列最大值不在
while (!pq.isEmpty() && pq.peek() < left) {
pq.poll();
}
// 如果窗口形成
if (left >= 0) {
res[left] = nums[pq.peek()];
}
}
return res;
}
}
时间复杂度：O(nlogn) 当数组是单调递增的情况下，所有元素只入队不出队，而优先级队列由于入队时需要排序，所以入队的时间复杂度为 O(logn)，因此总的时间复杂度为 O(nlogn)空间复杂度：O(n)
- 方法三：单调队列
思路：我们顺着方法二的优先级队列继续优化。
可以考虑这样一种情况，存在下标 i 和 j，它们之间存在这样的关系：nums[i] <= nums[j] 且 i < j。由于窗口是从左到右滑动的，所以下标小的 i 对应的元素先出窗口，而且由于 nums[i] <= nums[j] ，所以那也就意味着只要 nums[i] 和 nums[j] 都在窗口内，nums[i] 就不可能时最大值。所以当 nums[j] 出现在出口内时，我们可以将 nums[i] 永久地从出口内移除。因此我们可以用一个单调队列存储 nums 数组的下标，队列中的下标是从小到大存储的，且这些下标对应的值在 nums 数组中严格单调递减的——在窗口滑动过程中，如果当前下标所对应的值大于队尾下标对应的值，则队尾出队，直至队列为空或者队尾下标对应的值不小于当前下标所对应的值，将当前下标入队。由于队列中的下标对应的值是严格单调递减的，因此此时队首对应的元素就是滑动窗口的最大值。且与方法二相同的是，此时最大值可能不在滑动窗口内，所以在记录最大值的时候需要先判断此最大值是否还在窗口内。
代码
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
// 单调队列：队列中下标所对应的值在 nums 数组中严格单调递减
if (nums == null || nums.length < 1 || k < 1) {
throw new IllegalArgumentException();
}
int length = nums.length;
int[] res = new int[length - k + 1];
// 单调队列存储下标值，且下标对应的数值在 nums 中严格单调递减
Deque queue = new linkedList<>();
for (int i = 0; i < length; i++) {
int left = i - k + 1;
// 如果当前下标对应的值大于队尾下标对应的值，则队尾出队
while (!queue.isEmpty() && nums[i] > nums[queue.peekLast()]) {
queue.pollLast();
}
queue.offerLast(i);
// 在记录最大值之前先判断最大值是否还在窗口内
while (!queue.isEmpty() && queue.peekFirst() < left) {
queue.pollFirst();
}
// 如果窗口形成
if (left >= 0) {
res[left] = nums[queue.peekFirst()];
}
}
return res;
}
}
时间复杂度：O(n)空间复杂度: O(k)
- 方法四：单调队列（数组实现）
思路：与方法三思路一致，只不过这次我们用数组实现，效率更高。其中数组模拟队列的一些操作说明，可以戳这里数组模拟队列与单调队列求解滑动窗口
代码
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
// 单调队列：队列中下标所对应的值在 nums 数组中严格单调递减
if (nums == null || nums.length < 1 || k < 1) {
throw new IllegalArgumentException();
}
if (k == 1) return nums;
int length = nums.length;
int[] res = new int[length - k + 1];
// 单调队列存储下标值，且下标对应的数值在 nums 中严格单调递减
int[] queue = new int[length];
// head 为队列头指针，tail 为队列尾指针
int head = 0, tail = -1;
for (int i = 0; i < length; i++) {
// 窗口的左边界
int left = i - k + 1;
// 如果当前下标对应的值大于队尾对应的值，则队尾出队
while (head <= tail && nums[i] > nums[queue[tail]]) {
tail--;
}
queue[++tail] = i;
// 如果队列头不在窗口内
if (queue[head] < left) {
head++;
}
// 如果窗口形成，则记录最大值
if (left >= 0) {
res[left] = nums[queue[head]];
}
}
return res;
}
}
时间复杂度: O(n)空间复杂度：O(n) 参考
数组模拟单调栈和单调队列数组模拟队列与单调队列求解滑动窗口滑动窗口最大值官方题解
