Sliding Window Algorithm滑动窗口算法-Java快速进阶教程

1. 概述

在处理需要检查给定数组中某些范围的答案的问题时，滑动窗口算法可能是一种非常强大的技术。

在本教程中，我们将解释滑动窗口技术及其变体，即固定窗口大小和灵活窗口大小。此外，我们将提供两种变体的示例，以便更好地理解。

2. 理论思想

滑动窗口技术背后的主要思想是将两个嵌套循环转换为单个循环。通常，该技术可以帮助我们将时间复杂度从 降低到

。

使用滑动窗口技术的条件是，问题要求为函数查找最大值（或最小值），该函数重复计算数组中一组范围的答案。也就是说，如果这些范围可以根据它们的开始进行排序，并且它们的结束也变得排序，那么我们可以使用滑动窗口技术。

换句话说，必须满足以下条件：如果

那么可以得到

，其中

区间的左侧，并且

和

是同一个区间的左侧末端。

基本上，这种技术允许我们迭代包含两个指针L和R的数组。这两个指针分别表示当前范围的左端点和右端点。在每一步中，我们要么就不移动L、R，要么将它们两个全都移动到下一个范围。

为此，我们必须能够在R向前移动时向当前范围添加元素。此外，还必须能够在向前移动L时从当前范围中删除元素。每次到达某个范围时，我们就根据当前范围内的元素计算答案。

如果范围的长度是固定的，我们称之为固定大小的滑动窗口技术。然而，如果改变了范围的长度，我们称之为灵活窗口大小技术。我们将提供这两种选项的示例。

3.固定大小的滑动窗口

让我们看一个例子来更好地理解这个想法。

3.1. 问题

假设问题给我们一个长度为n和数字k的数组。问题要求我们找出数组中连续的k个元素的最大和。

换句话说，首先，我们需要计算数组中所有长度为k的范围的和。然后，我们必须返回所有计算出来的和中的最大和。

3.2. 朴素法

让我们来看看解决这个问题的朴素法：

首先，遍历所有可能的起始区间。对于每个区间，我们从L到L + k - 1遍历其元素，并计算它们的和。在每一步之后，我们更新到目前为止的最佳答案。最后，这个答案会变成原来的答案与当前计算结果之间的最大值。

最后，我们返回在所有范围中找到的最佳答案。

在最坏情况下，时间复杂度为O(n^2)，其中n是数组的长度。

3.3. 滑动窗口算法

让我们尝试改进我们的原始方法以达到更好的复杂度。

首先，让我们找出两个连续区间之间的关系。第一个范围显然是[1,k]。但是，第二个范围将是[2,k+1]。

为了从第一个区间移动到第二个区间，我们执行了两个操作:第一个操作是将索引为k+1的元素与答案相加。第二个操作是从答案中删除索引为1的元素。

每次，在我们计算出相应范围的答案后，我们只是最大化我们计算出的总答案。

让我们看看上述问题的解决方案:

首先，我们计算第一个范围[1,k]的和。其次，我们将其和存储为到目前为止的答案。

然后，遍历区间[k+1, n]的所有可能的端点。在每一步中，我们更新当前范围的和。因此，我们增加索引i处元素的值，并删除索引i-k处元素的值。

每次，我们更新到目前为止找到的最佳答案，使其成为原始答案和新计算的总和之间的最大值。最后，我们返回在所有测试范围中找到的最佳答案。

该方法的时间复杂度为O(n)，其中n是数组的长度。

4. 灵活大小的滑动窗口

我们将灵活大小的滑动窗口技术称为双指针技术。我们也将以这种技术为例来更好地解释它。

4.1. 问题

假设我们有n本书排成一行。对于每一本书，我们知道阅读它所需的分钟数。然而，我们只有k分钟的空闲时间来阅读。

此外，我们应该读一些连续的书从行。换句话说，我们可以从一行的书中选择一个范围来阅读它们。当然，条件是阅读这些书所需的时间总和不能超过k。

因此，这个问题要求我们找到我们可以阅读的书的最大数量。也就是说，我们需要从数组中找到一个和不超过k的范围，以便这个范围的长度是可能的最大值。

4.2. 朴素法

看看解决问题的朴素法：

首先，我们用0初始化到目前为止最好的答案。接下来，遍历范围的所有可能起点。对于每个开始，我们向前迭代，直到我们可以阅读更多的书。一旦我们无法再阅读更多的书，我们就更新最佳答案，使其达到旧答案和我们找到的范围长度之间的最大值。

最后，我们返回我们设法找到的最佳答案。

这种方法的复杂度是O(n^2)，其中n是图书数组的长度。

4.3. 滑动窗口算法

我们将尝试改进原始方法，以获得线性复杂度。

首先，假设我们成功地找到了从数组开头开始的范围的答案。下一个范围从数组中的第二个索引开始。但是，第二个范围的结束肯定在第一个范围结束之后。

原因是第二个范围没有使用第一个元素。因此，第二个范围可以进一步扩展它的末端，因为它现在有更多的空闲时间可以使用。

因此，当从一个范围移动到另一个范围时，我们首先删除当前答案的旧开头。此外，我们尝试尽可能地扩展当前的范围。

因此，最后，我们将遍历所有可能的范围，并存储找到的最佳答案。

下面的算法对应于刚才解释的想法:

与简单的方法一样，我们遍历范围的所有可能的起点。对于每个起点，我们首先从当前和中减去下标L-1的值。

之后，我们将尽可能地移动R。因此，只要和仍然不超过k，我们就继续移动R。最后，更新到目前为止的最佳答案。由于当前范围的长度是R-L，我们用这个值最大化最佳答案。

虽然该算法的复杂度看起来是O(n^2)，但我们还是要仔细分析一下该算法。变量R总是保持它的值。因此，它只会向前移动，直到达到n的值。因此，我们总共执行while循环的次数最多为n次。

因此，该方法的复杂度为O(n)，其中n是数组的长度。

5. 差异

主要的区别在于，在一些问题中，我们被要求在相同大小的所有范围中检查某个属性。另一方面，在其他一些问题中，要求在满足一定条件的所有范围中检查某个性质。在这些情况下，这种情况可能会使范围的长度发生变化。

如果这些范围的大小已知(比如连续元素的问题)，我们肯定会使用固定大小的滑动窗口技术。但是，如果区间的大小不同(比如书长的问题)，我们肯定会使用可变大小的滑动窗口技术。

此外，在使用我们在开头介绍的滑动窗口技术时，一定要记住以下条件:我们必须保证向前移动L指针一定会使R保持在原来的位置，或者也会将其向前移动。

6. 结论

在本教程中，我们解释了滑动窗口方法。为该技术提供了理论思路。此外，我们还介绍了固定大小和可变大小滑动窗口技术的两个示例。最后，我们解释了何时使用每种技术。