滑动窗口算法（Sliding Window Algorithm）

小甲鱼

滑动窗口算法（Sliding Window Algorithm）

介绍

滑动窗口算法（Sliding Window Algorithm）是一种常用的优化算法，主要用于解决一些数组、列表或字符串等线性结构上的问题。

该算法的主要思想是维护一个动态的窗口，窗口在数据结构上前进（或滑动）并根据需要改变其大小。

这样可以有效地减少不必要的计算和数据处理，从而优化性能。

对于某些问题，该算法可以将将原先 O(n²) 或 O(n³) 降低到 O(n) 的时间复杂度。

还是蛮有料的~




原理

滑动窗口算法的基本思想是使用一个窗口在数据（如数组或列表）上滑动，并在滑动过程中保持和更新一些有用的状态信息。

滑动窗口可以看作是一个队列，可以从一端添加元素，从另一端删除元素。

当窗口向右移动时，一些元素会进入窗口，一些元素会离开窗口。

在每一步，我们都可以根据新加入的元素和离开的元素更新我们的状态。


演示

比如我们要从 100 个数中找出相邻 3 个数的最大和，那么滑动窗口就非常合适了：

如果无法播放，请点击此处在新窗口打开

实现

那么现在有 100 个数字如下：

1. 2 4 0 9 4 0 4 3 1 2
   
2. 0 0 6 3 3 3 3 6 4 6
   
3. 5 2 8 5 4 5 8 0 7 8
   
4. 5 6 9 2 4 8 9 7 1 3
   
5. 4 9 5 1 1 6 2 0 1 9
   
6. 8 3 3 3 0 2 5 8 3 7
   
7. 7 1 3 3 6 7 9 6 2 1
   
8. 8 5 8 4 0 9 2 5 0 0
   
9. 5 9 1 5 2 7 9 8 5 9
   
10. 6 2 4 1 7 2 9 4 0 0

复制代码

请用代码来找出相邻 3 个数的最大和，你可以做到吗？

游客，如果您要查看本帖隐藏内容请回复

Sayuqwq

Axiujiu

太巧了，刚刚看到移动窗口函数

欧拉计划

滑动窗口算法确实优秀~

左右丶

太巧了，刚刚看到移动窗口函数