问题引入

【问题】 有一个整型数组arr和一个大小为w的窗口从数组的最左边滑到最右边，窗口每次 向右边滑一个位置。 例如，数组为[4,3,5,4,3,3,6,7]，窗口大小为3时: [4 3 5]4 3 3 6 7 4[3 5 4]3 3 6 7 4 3[5 4 3]3 6 7 4 3 5[4 3 3]6 7 4 3 5 4[3 3 6]7 4 3 5 4 3[3 6 7] 窗口中最大值为5 窗口中最大值为5 窗口中最大值为5 窗口中最大值为4 窗口中最大值为6窗口中最大值为7如果数组长度为n，窗口大小为w，则一共产生n-w+1个窗口的最大值。 请实现一个函数。 输入:整型数组arr，窗口大小为w。 输出:一个长度为n-w+1的数组res，res[i]表示每一种窗口状态下的 以本题为例，结果应该返回{5,5,5,4,6,7}。 【思路】 迅速得到窗口内的最大值： 使用一个双端队列，双端队列严格按照从大到小排。

数据增加： 若增加的数从尾进，若增加的数可以放在尾部，则放入，若无法放入，则将尾部数弹出，直到增加的数可以从尾部进入。 数据减少： 若过期的数的位置是双端队列的头部，则过期的数从头部弹出，若不是头部，则不弹出。

滑动窗口概述

【滑动窗口】 滑动窗口模式是用于在给定数组或链表的特定窗口大小上执行所需的操作，比如寻找包含所有 1 的最长子数组。从第一个元素开始滑动窗口并逐个元素地向右滑，并根据你所求解的问题调整窗口的长度。在某些情况下窗口大小会保持恒定，在其它情况下窗口大小会增大或减小。 下面是一些你可以用来确定给定问题可能需要滑动窗口的方法：

1. 问题的输入是一种线性数据结构，比如链表、数组或字符串
2. 你被要求查找最长/最短的子字符串、子数组或所需的值
3. 你可以使用滑动窗口模式处理的常见问题： 1）大小为 K 的子数组的最大和（简单） 2）带有 K 个不同字符的最长子字符串（中等） 3）寻找字符相同但排序不一样的字符串（困难） 【上面问题代码实现】

vector<int> SlidingWindowMaxArray(vector<int> Arr, int Window)
{
          
   
	//双向队列实现
	vector<int> res(Arr.size()-Window+1);
	if (Arr.size() < 0 || Window < 1 || Window > Arr.size())
		return res;
	deque<int> mydeque;	//队列里存放下标，不是当前数
	int index = 0;
	for (int i=0;i<Arr.size();i++)	//窗口的R的右边界
	{
          
   
		//i位置上的Arr[i]准备进窗口
		//队列不为空，而且不满足进入队列尾部条件（Arr[mydeque.back()]<=Arr[i]），弹出队列尾部元素
		while (!mydeque.empty() && Arr[mydeque.back()]<=Arr[i])	
		{
          
   
			mydeque.pop_back();//从尾部弹出，弹到不用弹或者弹空了，i进队列
		}
		mydeque.push_back(i);	//把地址i往进加
		if (mydeque.front()==i-Window)	//i-Window代表过期的下标
		{
          
   
			mydeque.pop_front();	//从头部弹出过期的下标
		}
		if (i>=Window-1)	//初始形成窗口
		{
          
   
			res[index++] = Arr[mydeque.front()];	//当前队列的头实际上就是当前窗口最大值
		}
	}
	return res;
}