什么是滑动窗口算法? 例子？

在解决一个几何问题时，我遇到了一种叫做滑动窗口算法的方法。

找不到任何相关的研究资料。

算法是关于什么的？

175883 次浏览
小开
最佳答案

一般来说，滑动窗口是在基础集合上运行的子列表。也就是说，如果你有一个像

[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]

例如，如果你想计算一个运行平均值，或者如果你想创建一个所有相邻对的集合，这是非常有用的。

小开

滑动窗口是一种解决涉及数组/列表问题的技术。这些问题在 O (n ^ 2)或 O (n ^ 3)中用蛮力方法很容易解决。利用“滑动窗口”技术，我们可以将时间复杂度降低到 O (n)。

这里有一篇很棒的文章: https://medium.com/outco/how-to-solve-sliding-window-problems-28d67601a66

所以你要做的第一件事就是找出一个问题 它使用了滑动窗口的范例。幸运的是，有一些共同的 赠品:

  • 这个问题将涉及一个数据结构，它像数组或字符串一样是有序和可迭代的

  • 您正在查找数组/字符串中的某个子范围，比如最长、最短或目标值。

  • 在 O (N2)、 O (2 ^ N)或其他一些大的时间复杂度中，存在一个明显的幼稚或蛮力解决方案。

但是最大的漏洞是你要找的东西是 通常是某种最优的，比如最长的序列或者最短的序列 完全满足给定条件的事物的序列。

小开

为了补充以前的答案这里有一些更多的资源，说明这个概念非常好。

这个 youtube 视频 是我在这个话题上找到的最好的视频。

这里 是关于 leetcode 的问题列表，这些问题可以用这种技术来解决

滑动窗口是最常见的话题之一，这是在顶级公司的编码轮询问，所以它绝对值得花一些时间来掌握这一点。

小开

我认为它更像是一种技术而不是算法。这种技术可以应用在各种算法中。

我认为通过下面的例子可以更好地理解这种技术，假设我们有这样一个数组:

[ 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。我们已经走到了尽头，所以我们结束了。

以暴力方式按方案执行这项规定的做法如下:

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;
};

这个问题的时间复杂度是多少？是 O(n*k)。外部循环通过 n - k + 1项，但是当 n比 k大得多时，我们可以忘记 k + 1部分，只称它为 n项。然后内部循环是通过 k项，所以我们有 O(n*k)。试着把它想象成这样:

enter image description here

我们能把这个数字降到 O(n)吗? 让我们回到这个数组:

[ 5, 7, 1, 4, 3, 6, 2, 9, 2 ]

首先我们得到 5, 7, 1, 4, 3的总和。接下来我们需要 7, 1, 4, 3, 6的总和。像这样想象它，用一个“窗口”围绕每组五个元素。

enter image description here

第一个窗口和第二个窗口有什么区别？第二个窗口去掉了左边的 5但在右边增加了 6。因为我们知道第一个窗口的和是 20为了得到第二个窗口的和我们取 20减去 5再加上 6得到 21。我们实际上并不需要遍历第二个窗口中的每个元素并将它们相加(7 + 1 + 4 + 3 + 6)。这将涉及到重复和不必要的工作。

这里的滑动窗口方法最终是两个操作而不是五个，因为 k是 5。这不是一个巨大的改进，但你可以想象，对于较大的 k(和较大的 n) ，它确实有帮助。

enter image description here

下面是使用滑动窗口技术编写代码的方法:

const getLargestSumOfFiveConsecutiveElements = (arr) => {
let currSum = getSum(arr, 0, 4);
let largestSum = currSum;


for (let i = 1; i <= arr.length - 5; i++) {
currSum -= arr[i - 1]; // subtract element to the left of curr window
currSum += arr[i + 4]; // add last element in curr window
largestSum = Math.max(largestSum, currSum);
}


return largestSum;
};


const getSum = (arr, start, end) => {
let sum = 0;


for (let i = start; i <= end; i++) {
sum += arr[i];
}


return sum;
};

这就是滑动窗口技术的要点。在其他问题中，您可能要做一些比得到窗口内部元素之和更复杂的事情。或者窗户本身可能是不同大小的，而不是我们在这里看到的固定大小的5。但是，滑动窗口技术的这个基本应用应该为您提供一个基础，您可以在此基础上进行构建。


提交答案