滑动窗口算法

如果你学习计算机科学，无疑会遇到几种算法。滑动窗口算法是一种应用于数据传输和计算机网络等领域的技术。它用于 TCP（传输控制协议）中的流量控制。此外，这种方法还可以用于构建各种竞赛题目。因此，为了在面试中获得理想的工作，最好理解这种算法。本文涵盖了滑动窗口算法及其在三种不同编程语言中的实现。

滑动窗口算法是一种降低算法复杂度的方法。它的使用方式是减少循环次数，从而优化程序。在此方法中，上一步的结果用于计算下一步的结果。

窗口滑动方法旨在用单个循环替换嵌套循环，并减少耗时的计算次数。

范围

本文介绍了滑动窗口算法及其使用示例。文章中还包含了解决滑动窗口问题的步骤。

• 本文中多次演示了滑动窗口方法。

滑动窗口算法：它是什么？

想象一条长长的链条。与其从上方倒油，不如考虑用手来给整条链条上油。

一种方法是拿起一些油，涂抹在链条的一部分上，再拿起一些油，涂抹在下一个尚未涂抹油的区域，以此类推，直到整个链条都被润滑。

您也可以通过将一块布浸入油中，然后用它抓住链条的一端来做到这一点。与其反复浸布，不如用一只手将其滑动到下一部分，然后是下一部分，直到到达另一端。

第二种方法称为“滑动窗口技术”，从一端滑动到另一端的部件称为“滑动窗口”。

通过这种技术，我们可以快速计算具有固定计算窗口的项目，并比嵌套循环（朴素方法）更有效地获得结果。该算法的主要目标是利用一个窗口的结果来计算下一个窗口的结果。

假设有一群 12 位朋友决定一起举办派对，但主要问题是谁来买单。经过一番讨论，他们决定，由于他们围坐在一张圆桌旁，年龄最大的三个人组成的组合将负责支付账单。

朴素的方法是遍历每个人，然后遍历接下来三个人的年龄来找到那个组合，但这需要 O(12*3) 的时间。滑动窗口方法允许我们将这个问题从 O(12*3) 缩小到 O(12)。我们将在下一节中了解如何使用滑动窗口方法解决此问题。

使用滑动窗口方法的先决条件

在一种特殊情况，即在整个嵌套循环中计算窗口大小时，可以使用滑动窗口方法。此时才能降低时间复杂度。

滑动窗口技术：我该如何使用它？

以下示例演示了滑动窗口方法的通用用法：

1. 确定所需的窗口大小。
2. 从数据结构的开头开始，计算第一个窗口的结果。
3. 然后，通过循环将窗口移动 1，并逐个窗口地继续计算结果。

在前面给出的例子中，我们可以应用滑动窗口方法。

我们将首先将三个成员的总年龄相加，然后我们将继续添加下一个并减去最后一个，以在每一步获得三个人的总年龄，然后我们可以进行比较。这里，窗口大小是 3，我们移动窗口来计算下一组的年龄总和。这是一个完整的滑动窗口算法，时间复杂度为 O(12)。该方法中每次滑动的部分是滑动窗口，可用于解决大多数滑动窗口问题。

假设学生年龄范围是 [21, 23, 24, 22, 21, 26, 23, 22, 21, 24, 20]

而相邻三人的各种窗口是 [21,23,24], [23,24,22], [24,22,22], [22,22,21], [22,21,26], [21,26,23], [26,23,22], [23,22,21], [22,21,24], 和 [21,24,20]。

在这里，所有和都是使用滑动窗口方法计算的；让我们看看我们的策略。

前三个相加为 21+23+24 = 68，接下来的三个相加为 68-21+22 = 69，69-23+22 = 68，依此类推，直到最后一个。通过比较每一步计算出的数量，可以找到所需的结果。

滑动窗口问题的简单解决方案

以下是应用滑动窗口技术的步骤：

1. 确定算法必须运行的窗口大小。
2. 确定第一个窗口的结果，就像我们在朴素方法中所做的那样。
3. 将光标保持在起始位置。
4. 接下来，执行一个循环，一次向前移动窗口一步，一次向前移动光标，并记录每个窗口的结果。

让我们探讨如何使用这些过程来解决滑动窗口问题。假设我们必须确定整数数组 arr（大小为 n）中 m 个元素的最大和。

示例

• 如果 n = 5 且 arr[5] = 10, 20, 10, 30, 5，则答案为 60 (20 + 10 + 30)。
• 如果 n = 7 且 arr[7] = 2, 10, 17, 1, 9, 13, 4，且 m = 4，则答案为 40 (17+1+9+13)。

此问题的一个简单解决方案是为每个元素执行一个循环，然后是另一个嵌套循环来计算接下来 m 个项目的总和，并在每个阶段保留最大值。

使用滑动窗口技术开发优化方法

我们如何使用滑动窗口方法计算结果？

• 我们计算数组的前 m 个元素的总和，并将结果保存在一个名为 running_sum 的变量中。
• 之后，我们将移动窗口，在线性扫描数组直到末尾，并跟踪 maximum_sum，每次将其与 running_sum 进行比较。
• 当我们每次获得一个窗口的 m 个项目总和时，我们将添加下一个元素，移除第一个元素，然后将第一个指针提高。
• 每次，这将为我们提供 maximum_sum。

问题陈述

在继续问题方法之前，让我们先理解它。给定一个大小为 N 的数组，找出 K 个连续元素的总和最大的问题。需要帮助理解吗？别担心，我们将通过一个例子来理解这一点。

假设给定了以下数组，并被告知找出三个连续整数的总和最大。在这种情况下，K 等于 3。

arr = [16, 12, 9, 19, 11, 8]

提供的数组中以下三个连续条目的块是：[16, 12, 9], [12, 9, 19], [9, 19, 11], 和 [19, 11, 8]。现在我们已经计算了每个块的总和，如下所示：37, 40, 39, 和 38。所有这些估计数量中最大的总和是四十。因此，40 是我们的输出。

朴素策略

有一个简单但效率不高的解决方案。你可能会问，既然这个策略效率不高，为什么还要讨论它。一个人必须了解一个好策略的价值，对吧？此外，通过理解这个策略，我们可以通过构建更有效的算法——滑动窗口方法来扩展我们的专业知识。

使用此方法，我们从第一个索引开始，一直加到第 k 个元素。我们对所有可能的 k 个连续块或 k 个项目组重复此操作。此方法使用嵌套 for 循环；外部 for 循环从 k 个元素块的第一个元素开始，一直运行到第 k 个元素。

由于此方法使用两个嵌套循环，其复杂度为 O(N*K)。其中 k 是要考虑的连续子条目数，n 是给定的数组大小。当我们告诉你这项工作可以很快完成时，你可能不相信？在这里自己查看一下。

滑动窗口技术

让我们用一个类比来帮助我们理解这个策略。考虑一个固定在长度为 n、宽度为 k 的窗口中的面板。目前，面板距离中心为 0 个单位，即最左边。将窗口中的 n 元素数组 arr[] 与面板中的 k 元素当前总和合并。如果我们施加力，窗口将向前移动一个单位距离。面板将覆盖接下来的 k 个元素。

每次将当前块的最后一个元素添加进去，并将前一个块的第一个元素减去，以获得当前总和。我完成了！整个滑动窗口算法看起来就是这样。很简单，不是吗？现在让我们来看看这种方法的算法。

窗口滑动算法

使用滑动窗口算法的步骤如下：

1. 计算前 K 个元素的总和，并将其存储在 current 变量中。将其保存在 maximum sum 变量中，因为它是初始总和，因此是当前的最高值。
2. 考虑到窗口大小为 K，我们将窗口向右移动并计算窗口的项目总和。
3. 如果 current 超过 maximum sum，则步骤 3 更新 maximum，然后重复步骤 2。

示例

现在我们有了一个例子，让我们进一步理解这种方法。maximum sum 变量的初始值为 0，然后开始该过程。在这种情况下，也假定 k 为 3。

我们从计算前三个连续整数的总和开始，即索引 0 到 2 的数字。这个第一个窗口的总和是 37，保存在 current 变量中。由于 current 现在超过了 maximumSum，maximumSum 变量的值被修改以记录 37。

通过将窗口滑动一个单位距离来覆盖接下来的三个数字。通过从 current 中减去 16 并加上 19，计算出新的 current 窗口的总和。40 是 current 的当前值。由于与 maximumSum 相比，最近的 current 值更大，因此 40 将存储在 maximumSum 变量中。

再次移动窗口以覆盖接下来的 3 位数字。此时，总和计算为 39，这是此窗口的总和。由于此数量小于 maximumSum，maximumSum 的值保持不变。

现在一个新窗口覆盖了最后三个数字。此时，计算出的总和为 38。此变量的值不受影响，因为它低于 maximumSum（40）的值。现在已经考虑了所有三个连续数字的组合，并计算了它们的总和。最后，返回最大总和 40。

Python 中的滑动窗口算法

输出

40

C++ 滑动窗口算法

输出

40

Java 中的滑动窗口算法

输出

40

复杂时间

鉴于我们在前面提到的技术中使用单个循环来计算最大总和，因此代码的时间复杂度为 O(N)。

结论

滑动窗口算法是竞赛编程的一个重要主题。通过对算法进行一些小的调整，可以解决许多问题。在本文中，我们首先识别问题陈述，然后识别简单的解决方案。最后，我们学习了一种更有效的方法及其 C++、Java 和 Python 的源代码。我们的专业人员全天候提供服务，帮助您解决可能遇到的任何代码问题。

• 滑动窗口算法得到广泛使用，用于任何问题解决或算法分析的窗口大小在整个程序中保持不变。然后可以使用滑动窗口技术优化朴素方法，并降低复杂度。
• 该滑动窗口算法的时间复杂度，其中 N 是存在的项数，为 O(N)。
• 当窗口大小固定时，必须始终使用它。
• 根据我们的偏好和任务要求，我们可以以各种方式实现此算法，例如从右向左或从左向右迭代。