什么是滑动窗口算法？例子？
Sil*_*ter 48 algorithm sliding-window
在解决几何问题时,我遇到了一种称为滑动窗口算法的方法.
无法真正找到任何研究材料/细节.
算法是什么？
aio*_*obe 112
一般而言,滑动窗口是在底层集合上运行的子列表.即,如果你有像这样的阵列
[a b c d e f g h]
一个大小为3的滑动窗口就像是一样
[a b c]
[b c d]
[c d e]
[d e f]
[e f g]
[f g h]
如果您想要计算运行平均值,或者如果要创建一组所有相邻对等,这将非常有用.
- 你的问题有点不清楚，但假设你有以下情况：“[5, 10, 7, 13, 19, 14, 3, 13, 17, 10, 22, 2]”为一月，二月，...... ，十二月。如果你的窗口大小是 4，那么年中将会有这个窗口：`[19, 14, 3, 13]`。就这样。例如，如果您计算运行平均值，年中的平均值将为“(19+14+3+13)/4”。这是否回答你的问题？ (2认同)
Ada*_*ner 98
我认为它更像是一种技术而不是一种算法。这是一种可用于各种算法的技术。
我认为通过以下示例可以最好地理解该技术。想象一下我们有这个数组：
[ 5, 7, 1, 4, 3, 6, 2, 9, 2 ]
我们如何找到五个连续元素的最大和？好吧，我们首先看看5, 7, 1, 4, 3总和是20。然后我们将查看下一组五个连续元素，即7, 1, 4, 3, 6。这些的总和是21。这比我们之前的总和还多，所以7, 1, 4, 3, 6是目前我们得到的最好的总和。
让我们看看我们是否可以改进。1, 4, 3, 6, 2? 不，总计为16。4, 3, 6, 2, 9? 总和为24，所以现在这是我们得到的最好的序列。现在我们继续下一个序列，3, 6, 2, 9, 2。总和为22，这并没有击败我们目前最好的24。我们已经走到了尽头，所以我们完成了。
在代码中实现这个的蛮力如下：
[ 5, 7, 1, 4, 3, 6, 2, 9, 2 ]
这个的时间复杂度是多少？它是O(n*k)。外循环正在遍历n - k + 1项目，但是当n它比 大得多时k，我们可以忘记该k + 1部分而将其称为n项目。然后内部循环遍历k项目，所以我们有O(n*k). 试着像这样想象它：
我们可以把它归结为仅仅O(n)吗？让我们回到这个数组：
[ 5, 7, 1, 4, 3, 6, 2, 9, 2 ]
首先我们得到 的总和5, 7, 1, 4, 3。接下来我们需要求和7, 1, 4, 3, 6。像这样想象它，每组五个元素周围都有一个“窗口”。
第一个窗口和第二个窗口有什么区别？好吧，第二个窗口去掉5了左边的，但6在右边添加了一个。因此，由于我们知道第一个窗口的总和是20，为了得到第二个窗口的总和，我们取它20，减去5，然后加上6得到21。我们实际上不必遍历第二个窗口中的每个元素并将它们相加 ( 7 + 1 + 4 + 3 + 6)。这将涉及重复和不必要的工作。
这里滑动窗口方法最终是两个操作而不是五个操作，因为k是5。这不是一个巨大的改进，但您可以想象，对于更大k（和更大n）它确实有帮助。
以下是使用滑动窗口技术的代码的工作方式：
const getMaxSumOfFiveContiguousElements = (arr) => {
let maxSum = -Infinity;
let currSum;
for (let i = 0; i <= arr.length - 5; i++) {
currSum = 0;
for (let j = i; j < i + 5; j++) {
currSum += arr[j];
}
maxSum = Math.max(maxSum, currSum);
}
return maxSum;
};
这就是滑动窗口技术的要点。在其他问题中，您可能会做一些比获取窗口内元素的总和更复杂的事情。或者窗口本身可能有不同的大小，而不是我们在这里看到的固定大小的五个。但是滑动窗口技术的这个基本应用应该为您提供一个可以构建的基础。
- 令人惊叹的插图。感谢您抽出时间来做这件事。 (10认同)
- 这应该被接受的答案 (7认同)
- @PartOfTheOhana 我使用了 [Sketch](https://www.sketch.com/)，它是 Photoshop 的轻量级版本。作为替代方案，我最近遇到了 [Excalidraw](https://excalidraw.com/)，它是免费的，而且对于此类可视化来说似乎也是一个不错的选择。 (4认同)
- @Ezio 我真的很感谢你的赞美，谢谢。弄清楚这样的插图确实是我必须自己做才能理解它的事情:) (3认同)
- 绝对地。我们是计算机程序员，但我们必须掌握使用笔和纸解决问题的艺术。 (2认同)
要添加到前面的答案，这里有一些更多的资源，它们很好地说明了这个概念。
这个 youtube 视频是我在这个主题上找到的最好的视频。
以下是可以使用此技术解决的关于 leetcode 的问题列表
滑动窗口是顶级公司在编码轮次中被问到的最常见的主题之一，因此绝对值得花一些时间来掌握它。
对于涉及数组/列表的问题，滑动窗口是一种解决问题的技术。使用O（n ^ 2）或O（n ^ 3）中的蛮力方法可以轻松解决这些问题。 使用“滑动窗口”技术，我们可以将时间复杂度降低为O（n）。
伟大的文章在这里：https：//medium.com/outco/how-to-solve-sliding-window-problems-28d67601a66
因此，您要做的第一件事就是识别使用滑动窗口范式的问题。幸运的是，有一些常见的赠品：
问题将涉及一个有序且可迭代的数据结构，如数组或字符串
您正在该数组/字符串中寻找某个子范围，例如最长，最短或目标值。
在O（N²），O（2 ^ N）或其他一些大时间复杂度下，有一个很简单的幼稚或蛮力解决方案。
但是最大的礼物是，您正在寻找的东西通常是某种最优的，例如恰好满足给定条件的事物的最长序列或最短序列。