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

Question

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

真的找不到任何关于它的学习 Material /细节。

算法是关于什么的？

Answer 1

我认为它更像是一种技术而不是一种算法。这是一种可用于各种算法的技术。

我认为通过以下示例可以最好地理解该技术。假设我们有这个数组:

[ 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)。尝试像这样想象它:

我们能否将其简化为 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 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;
};

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