算法-滑动窗口.md

算法-滑动窗口

滑动窗口技术展示了如何将某些问题中的嵌套 for 循环转换为单个 for 循环以降低时间复杂度。

暴力方法

让我们从一个问题开始，说明我们可以在哪里应用这种技术：

问题：

给定一个大小为'n'的整数数组。

我们的目标是计算数组中'k'个连续元素的最大和。

Input  : arr[] = {100, 200, 300, 400}
         k = 2
Output : 700

Input  : arr[] = {1, 4, 2, 10, 23, 3, 1, 0, 20}
         k = 4 
Output : 39

我们通过相加子数组 {4, 2, 10, 23} 得到最大和

Input  : arr[] = {2, 3}
         k = 3
Output : Invalid

整个数组没有大小为 3 的子数组

让我们先用暴力方法分析问题，我们从第一个索引开始，求和到第 k 个元素。我们对所有可能的包含 k 个元素的连续块执行此操作。

该方法需要嵌套 for 循环，外部 for 循环从 k 个元素块的起始元素开始，内部嵌套循环相加到第 k 个元素。

可以参考以下实现：

// 暴力法
func MaxSumByForce(arr []int, n, k int) (maxSum int) {
	maxSum = 0

	for i := 0; i < n-k+1; i++ {
		currentSum := 0
		for j := 0; j < k; j++ {
			currentSum = currentSum + arr[i+j]
		}
		maxSum = int(math.Max(float64(currentSum), float64(maxSum)))
	}
	return
}

滑动窗口

最好利用计算系统总线中的窗格来理解滑动窗口技术，假设有一个长度 n 的总体窗口和长度固定为 k 的小窗口。

最开始的时候，该小窗口在总体窗口的最左侧，也就是从左边数的第 0 个单位。现在，将总体窗口与大小为 n 的数组 arr[] 进行联想，将子窗口与大小为 k 的数组进行联想。

现在，如果我们对子窗口发力，使它向前移动一个单位距离，该子窗口将覆盖接下来的 k 个连续元素。

假设有一个数组 arr[] = {5,2,-1,0,3}，k=3 , n=5

使用滑动窗口技术：

1. 我们使用线性循环计算 n 项中前 k 个元素的和，并将其存储在变量 window_sum 中

2. 然后我们将在数组上线性求和，直到子窗口达到末端，同时随时监控最大和

3. 为了获得 k 个元素块的当前和，只需从上一个块中减去第一个元素，然后添加当前块的最后一个元素

下面的图将清楚的说明窗口如何在数组上滑动。

首先我们从索引 0 开始计算初始窗口的和。在此阶段，窗口和为 6。现在，我们将最大和设置为当前窗口，也就是 6。

现在，我们按一个单元一个单元的索引来滑动窗口。现在我们从窗口中丢弃 5，并将 0 添加到窗口中。所以我们的窗口和现在变成了 1。因为这个和比较小，我们不会改变最大和。

同样的，现在我们再次将窗口按一个单元索引滑动，得到新的窗口和为 2。再次比较最大和，新的窗口和更小，所以我们不会改变最大值。因此，对于上述数组，我们的最大和为 6。

上述的操作可以用以下代码来实现：

// 滑动窗口
func MaxSumByWindowSliding(arr []int, n, k int) (maxSum int) {
	maxSum = 0

	for i := 0; i < k; i++ {
		maxSum = maxSum + arr[i]
	}

	windowSum := maxSum
	for i := k; i < n; i++ {
		windowSum = windowSum + arr[i] - arr[i-k]
		maxSum = int(math.Max(float64(windowSum), float64(maxSum)))
	}
	return
}