第 16 关 | 经典刷题思想之滑动窗口：1. 青铜挑战——滑动窗口其是很简单

我们在数组和链表部分研究过双指针思想，这里我们继续学习滑动窗口思想。 滑动窗口其实是双指针思想的一种特殊场景，由于这种方式能够很好的解决一些特定场景的问题，因此就有了“滑动窗口思想”。

1. 滑动窗口的基本实现

   在数组章节我们说过很多算法会大量移动数组中的元素，频繁移动元素会导致执行效率低下或者超时。使用两个变量能比较好的解决很多相关问题，在《一维数组》和《链表》章节我们介绍了很多典型例子，于是这种方式就慢慢演化成了“双指针思想”。 在数组双指针里，我们介绍过“对撞型”和“快慢型”两种方式，而滑动窗口思想其实就是快慢型的特例。学过计算机网络的同学都知道滑动窗口协议（Sliding Window Protocol），该协议是TCP实现流量控制等的核心策略之一。事实上在与流量控制、熔断、限流、超时等场景下都会首先从滑动窗口的角度来思考问题，例如hystrix、sentinel等框架都使用了这种思想。 滑动窗口的思想非常简单，如下图所示，假如窗口的大小是3，当不断有新数据来时，我们会维护一个大小为3的一个区间，超过3的就将新的放入老的移走。 这个过程有点像火车在铁轨上跑，原始数据可能保存在一个很大的空间里(铁轨)，但是我们标记的小区间就像一列长度固定的火车，一直向前走。 有了区间，那我们就可以造题了，例如让你找序列上三个连续数字的最大和是多少，或者子数组平均数是多少（LeetCode643）等等。

   

   从上面的图可以看到，所谓窗口就是建立两个索引，left和right，并且保持{left,right}之间一共有3个元素，然后一边遍历序列，一边寻找，每改变一次就标记一下当前区间的最大值就行了。 这个例子已经告诉我们了什么是窗口、什么是窗口的滑动： ●窗口： 窗口其实就是两个变量left和right之间的元素，也可以理解为一个区间。窗口大小可能固定，也可能变化，如果是固定大小的，那么自然要先确定窗口是否越界，再执行逻辑处理。如果不是固定的，就要先判断是否满足要求，再执行逻辑处理。 ●滑动： 说明这个窗口是移动的，事实上移动的仍然是left和right两个变量，而不是序列中的元素。当变量移动的时，其中间的元素必然会发生变化，因此就有了这种不断滑动的效果。 在实际问题中，窗口大小不一定是固定的，我们可以思考两种场景： 1固定窗口的滑动就是火车行驶这种大小不变的移动 。 2可变的窗口就像两个老师带着一队学生外出，一个负责开路，一个负责断后，中间则是小朋友。两位老师之间的距离可能有时大有时小，但是整体窗口是不断滑动的。 根据窗口大小是否固定，可以造出两种类型的题：

滑动窗口题目本身没有太高的思维含量，但是实际在解题的时候仍然会感觉比较吃力，主要原因有以下几点：

最后一个问题，那双指针和滑动窗口啥区别呢？根据性质我们可以看到，滑动窗口是双指针的一种类型，主要关注两个指针之间元素的情况，因此范围更小一些，而双指针的应用范围更大，花样也更多。

2. 两个入门题

   滑动窗口在不同的题目里，根据窗口大小变或者不变，有两种类型。 这里我们就看两个基本的题目。

   2.1. 子数组最大平均数

   LeetCode 674.最长连续递增序列 给定 n 个整数，找出平均数最大且长度为 k 的连续子数组，并输出该最大平均数。

   其中 1= nums[right]){ left = right; } right++; res = Math.max(res,right - left); } return res; } }

3. 通关文牒

   本文的重点就是理解滑动窗口的原理，将上面的内容理解清楚。