滑动窗口机制_c语言 一只贪吃的猴子,来到一个果园,发现许多串香蕉排成一行, 这个题的解题思路

相关系列文章

滑动窗口机制

目录

1.引言

2.概念

3.实际使用

4.理解

4.1.窗口和滑动的含义

4.2.注意事项

4.3.双指针和滑动窗口区别

5.入门小题

5.1.子数组的最大平均数

5.2.最长连续递增序列

5.3.贪吃的猴子

---

1.引言

算法四大思想：滑动窗口、贪心、回溯、动态规划。现在我们讲的是滑动窗口思想！

2.概念

在数组双指针里，我们介绍过"对撞型"和"快慢型"两种方式，而滑动窗口思想就是快慢型的特例。

3.实际使用

计算机网络中有滑动窗口协议（Sliding Window Protocol），该协议是TCP实现流量控制等的核心策略之一。事实上在流量控制、熔断、限流、超时等场景下都会首先从滑动窗口的角度思考问题，例如hystrix、sentinel等框架等都使用了这种思想。

4.理解

这个思想其实很好理解，如下图，假如窗口的大小是3，当不断有新数据来时，我们会维护一个大小为3的一个区间，超过3的就将新的放入老的移走。

这个过程有点像火车在铁轨上跑，原始数据可能保存在一个很大的空间里(铁轨)，但是我们标记的小区间就像一列长度固定的火车，一直向前走。

有了区间，就可以造题了，例如让你找序列上三个连续数字的最大和是多少、子数组平均数是多少等等。

4.1.窗口和滑动的含义

1. 窗口：窗口其实就是两个变量left和right之间的元素，也可以理解为一个区间。窗口大小不一定固定，思考两种场景：

• 如果是固定的，一般要先确定窗口是否越界，再执行逻辑处理。则一般会让你求哪个窗口的元素最大、最小、平均值、和最大、和最小等类型的问题

• 如果是可变的窗口，一般先判断是否满足要求，再执行逻辑处理。则一般要求一个序列里最大、最小窗口是什么

1. 滑动：说明这个窗口是移动的，事实上移动的仍然是left和right两个变量，而不是序列中的元素。当变量移动时，其中间的元素必然会发生变化，因此就有这种不断滑动的效果。

4.2.注意事项

1. 解题最终要落实到数组上，特别需要注意边界处理

2. 有些元素的比较、判断等比较麻烦，要借助集合等工具，而且处理过程中还有一些技巧（常见方法的使用等）

3. 堆，堆结构非常适合在流数据中找固定区间内的最大、最小等问题。因此滑动窗口经常和堆一起使用可以完美解决很多复杂问题.

4.3.双指针和滑动窗口区别

答：根据性质看到，滑动窗口是双指针的一种类型，主要关注两个指针之间元素的情况，范围更小一些，而双指针的应用范围更大，花样也更多。

5.入门小题

5.1.子数组的最大平均数

LeetCode 643：给你一个由 n 个元素组成的整数数组 nums 和一个整数 k。请你找出平均数最大且 长度为 k 的连续子数组，并输出该最大平均数。

先自己思考一下，不难但是想要完全做对还是要细心。例如我一开始就是先定义一个变量max保存最大值，然后left和right保存窗口两端。只要right不到数组边界，滑动窗口每次一变我就计算窗口内的元素之和，然后和max比较看看是否保存。

但是我一开始把max定为0，忽略数组内k个最大连续组序列的和是负数的情况。力扣上我又换回C++用INT_MIN来定义结果是直接超时了啊哈哈哈声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Gausst松鼠会/article/detail/513588