生成窗口最大数组（优先队列、单调队列）
问题重述：
给你一个整数数组 arr，有一个大小为 w 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值
示例 1：
输入：arr = [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
问题分析：
1.暴力求解：这道题可以使用暴力求解，直接在每一次窗口向右滑动时，遍历一遍数组，即可得出最大值数组，但这样时间复杂度为O（nk）
2.优先队列：我们可以使用记录每一个窗口的最大值，每一次向右移动窗口时，将当前值和上一个最大值进行对比，但是这样会产生一个问题，当上一个窗口的最大值处于窗口最左端时，此时我们向右滑动窗口会造成错误，最大值可能并不存在当前的窗口中，因此我们每一次向右滑动都对最大值队列进行判断，判断当前存放的上一个队列的最大值是否处于滑动窗口中，不处于则删除，处于则添加新增的值并进行判断（我们可以直接使用优先队列，设置好排序规则，添加时就不需要我们自己进行判断力），这种方法时间复杂组为O（nlogn）
3.单调队列：创建一个队列，每次添加时，进行条件判断，如果队列的尾部元素对应数值小于当前将要添加的数值，将当前队尾元素删除，直到大于等于为止，将当前数值对应元素加入队列。和优先队列一样，我们要判断最大元素对应值是否在窗口中，所以要进行判断。时间复杂度为O（N）
解题方法：
暴力求解、优先队列、单调队列
解题：
代码：
package cn.basic.algorithm;
import java.util.LinkedList;
import java.util.PriorityQueue;
/**
* @author FOLDN
* 生成窗口最大值数组
*/
public class MaxWindow {
public static void main(String[] args) {
int[] arr = {1,3,-1,-3,5,3,6,7};
int[] maxWindow = getMaxWindow1(arr, 3);
for (int i = 0; i < maxWindow.length; i++) {
System.out.print(maxWindow[i]);
}
}
// 优先队列
public static int[] getMaxWindow1(int[] arr,int w){
if (arr == null || w <1 || arr.length < w){
return null;
}
int[] maxArr = new int[arr.length - w +1];
//创建优先队列，定义比较规则（使用lambda表达式）
PriorityQueue<int[]> pq = new PriorityQueue<>((q1,q2)->q1[0] != q2[0] ? q2[0] - q1[0]: q2[1] - q1[1]);
//先将前w个元素进行比较
for (int i = 0; i < w; i++) {
pq.offer(new int[]{arr[i],i});
}
// 将前w个元素中最大值和下标加入优先队列
maxArr[0] = pq.peek()[0];
for (int i = w; i < arr.length; i++) {
// 将当前元素加入队列
pq.offer(new int[]{arr[i],i});
// 将不属于当前窗口的元素和下标删除
while (pq.peek()[1] <= i-w){
pq.poll();
}
// 将最大值加入最大值数组中
maxArr[i-w+1] = pq.peek()[0];
}
return maxArr;
}
// 单调队列(最优解)
public static int[] getMaxWindow2(int[] arr, int w){
if (arr == null || w <1 || arr.length < w){
return null;
}
int index = 0;
int[] maxArr = new int[arr.length - w +1];
LinkedList<Integer> qMax = new LinkedList<>();
for (int i = 0; i < arr.length; i++) {
// 将不满足条件的y
while (!qMax.isEmpty() && arr[qMax.peekLast()] < arr[i]){
qMax.pollLast();
}
qMax.addLast(i);
// 判断元素是否属于窗口中，这里的条件判断用while循环也可以
if (qMax.peekFirst() == i - w){
qMax.pollFirst();
}
if (i >= w -1){
maxArr[index++] = arr[qMax.peekFirst()];
}
}
return maxArr;
}
}
代码解析：
优先队列：
首先输入的值要满足题目条件，不满足条件则抛出异常或者返回空值。我们需要定义一个数组来存放每个窗口的最大值，该数组大小为**arr长度-w+1**。创建一个优先队列，在构造方法中重新定义**Comparator**来进行排序规则的设置。先比较前w个元素，然后从前w个元素在进行比较，在加入新元素后，每一次都要判断当前队列的头部元素是否属于当前窗口，如果不满足则删除，直到满足为止。然后就可以将当前队列头部元素对应的数值加入最大数组了（因为优先队列已经有顺序了）
单调队列：
首先输入的值要满足题目条件，不满足条件则抛出异常或者返回空值。我们需要定义一个数组来存放每个窗口的最大值，该数组大小为**arr长度-w+1**。创建一个单调队列（队列继承了**LindedList**，所以我们直接使用**LinkedList**也一样）。对数组进行循环，每一个元素添加前都对单调队列进行更新，始终保持当前要添加的元素小于当前元素，然后添加当前元素到队列尾部。当不满足条件时，删除队列尾部元素直到满足条件。添加完成后要记得保证当前的最大元素属于当前窗口中。
总结：
优先队列：Java中一种数据结构，可以通过我们自己定义排序规则（添加时会自动排序，不需要我们进行排序），当我们需要求某个元素的最大值最小值时就可以用到这种结构。
单调队列：队列内的元素按照规则排序，如果压入的元素不符合规则，则弹出队尾元素，直到满足规则。（头尾都可以删除，但是只有尾部才能添加）
拓展：单调栈
单调栈：栈内元素按照规则排序，如果压入的元素不符合规则，则弹出队尾元素，直到满足规则。（只能操作栈顶）
单调栈一般用于求距离自己较近的最大值或者最小值，单调队列一般用于维护某一段区间内的最大值或者最小值