一、滑动窗口是什么
滑动窗口是一种想象出来的数据结构：
滑动窗口有左边界L和有边界R
在数组或者字符串或者一个序列上，记为S，窗口就是S[L..R]这一部分
L往右滑意味着一个样本出了窗口，R往右滑意味着一个样本进了窗口
L和R都只能往右滑
二、滑动内最大值和最小值的更新结构
窗口不管L还是R滑动之后，都会让窗口呈现新状况，
如何能够更快的得到窗口当前状况下的最大值和最小值？
最好平均下来复杂度能做到O(1)
利用单调双端队列！
三、题目一
假设一个固定大小为W的窗口，依次划过arr，
返回每一次滑出状况的最大值
例如，arr = [4,3,5,4,3,3,6,7], W = 3文章来源：https://www.toymoban.com/news/detail-408984.html
返回：[5,5,5,4,6,7]文章来源地址https://www.toymoban.com/news/detail-408984.html
package class24;
import java.util.LinkedList;
/**
* 假设一个固定大小为W的窗口，依次划过arr，
* 返回每一次滑出状况的最大值
* 例如，arr = [4,3,5,4,3,3,6,7], W = 3
* 返回：[5,5,5,4,6,7]
*/
public class SlidingWindowMaxArray {
//滑动窗口技巧 定义一个双端队列linkedlist辅助滑动弹出元素加入元素 保存数组元素的下标
public static int[] getMaxWindow(int[] arr, int w){
//边界判断 如果数组空 窗口大小0 窗口大小大于数组 都是无效的 返回空
if(arr == null || w < 1 || arr.length < w) return null;
//定义一个双端队列 qmax 从大到小排序 头部大 尾部小 保存的是数组的元素索引 不是元素数值 因为根据滑动要把溢出的元素弹出 需要获取到索引
LinkedList<Integer> qmax = new LinkedList<>();
//定义一个数组 保存结果 每个窗口 3个元素中的最大值。 这里数组的长度是固定的
//数组长度8 窗口w=3 那么第一个窗口就是来到 4，3，5 返回5，第二个窗口时3，5，4 返回5，
// 第三个窗口 5，4，3 返回5...依次类推最后结果是[5,5,5,4,6,7] 长度6 即arr长度8 - w3 +1 =6
int[] res = new int[arr.length - w + 1];
int index =0; //定义结果集的下标从左到右
//从左到右开始遍历 直到遍历完整个数组
for(int r = 0; r < arr.length; r++){
//题意要求每个窗口返回其最大值 所以我们元素进队列，需要把前面小于等于的值都弹出来
//元素索引入队列前 需要判断 qmax非空时，如果当前数组arr[r]值大于等于队列尾部，
//就将尾部索引值弹出，直到队列前面的元素值大于当前arr[r]值即可
while(!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[r]){
qmax.pollLast();
}
//队列中弹出后，就可以将当前r索引入队列
qmax.addLast(r);
//判断当前队列头部是否需要弹出 一个窗口3长度 当r来到3时，窗口值就 1，2，3 就需要将r-w=0位置弹出
//如果r=5 那么窗口就是 3，4，5 队列中就需要将小于3的索引都去掉 因为要确保队列是保持着当前窗口最大值索引在队列头部的 超过了窗口的就要弹出
if(qmax.peekFirst() == r - w){
qmax.pollFirst(); //队列头部最大值的索引值如果不在当前窗口内 就需要弹出 避免影响当前窗口实际的最大值索引
}
//判断什么时候开始填入结果集，当我们r位置到达w窗口3个值长度时 就是第一个窗口的值需要填入了 0，1，2 也就是r=2时
if (r >= w - 1 ){
//也就是r>=2 后面开始每个值对应一个窗口 窗口最大值就是当前队列的头部 头部保持最大值的索引
res[index++] = arr[qmax.peekFirst()];
}
}
return res;
}
// 暴力的对数器方法
public static int[] right(int[] arr, int w) {
if (arr == null || w < 1 || arr.length < w) {
return null;
}
int N = arr.length;
int[] res = new int[N - w + 1];
int index = 0;
int L = 0;
int R = w - 1;
while (R < N) {
int max = arr[L];
for (int i = L + 1; i <= R; i++) {
max = Math.max(max, arr[i]);
}
res[index++] = max;
L++;
R++;
}
return res;
}
// for test
public static int[] generateRandomArray(int maxSize, int maxValue) {
int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) (Math.random() * (maxValue + 1));
}
return arr;
}
// for test
public static boolean isEqual(int[] arr1, int[] arr2) {
if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
return false;
}
if (arr1 == null && arr2 == null) {
return true;
}
if (arr1.length != arr2.length) {
return false;
}
for (int i = 0; i < arr1.length; i+到了这里，关于【算法&数据结构体系篇class24】：滑动窗口技巧的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
