滑动窗口最大值 (大小为 K 的所有子数组的最大值)

传统上，要找到数组中的最大元素，我们会使用一个循环遍历所有元素并返回该值。下面提供了伪代码实现。

伪代码

滑动窗口最大值技术是一种在给定大小的窗口中查找数组中每个窗口最大元素的方法。这项技术在许多应用中很有用，例如处理流式数据时，您需要在每一步中查找固定大小元素窗口中的最大元素。

要实现滑动窗口最大值技术，您可以使用嵌套循环方法，其中外层循环遍历数组中的窗口，内层循环查找每个窗口中的最大元素。或者，您可以使用堆等数据结构来跟踪每个窗口中的最大元素，从而降低算法的时间复杂度。

在这两种情况下，滑动窗口最大值技术的 time complexity 为 O(n) 或 O(nlogk)，具体取决于实现。

C 代码

输出

3 4 5 
Maximum element in the array: 5

说明

在此实现中，find_sliding_window_maximum 函数接收数组 arr、其大小 n 以及窗口大小 k。然后它遍历数组并查找大小为 k 的每个窗口中的最大元素。最后，它打印每个窗口中的最大元素并返回整个数组中的最大元素。

请注意，此实现的时间复杂度为 O(nk)，因为它使用嵌套循环来查找每个窗口中的最大元素。通过使用堆等数据结构来跟踪每个窗口中的最大元素，可以改进这一点，将时间复杂度降低到 O(nlogk)。

C++ 代码

输出

3 3 5 6 7

说明

此实现使用双端队列 (deque) 来存储数组元素的索引。deque 始终维护以下不变量：

deque 中的元素按非递减顺序排列，最大元素位于前面，最小元素位于后面。deque 中的元素位于当前窗口内。

这些不变量使我们能够在线性时间内有效地找到每个子数组的最大值。此实现的时间复杂度为 O(n)。

Java 代码

输出

3 3 5 5 6 7

Java 中的伪代码 (使用堆栈方法)

Python 代码

输出

3
3
4
5
5
5
6

C# 代码

输出

33
4
5
5
5
6

JavaScript 代码

输出

3
3
4
5
5
5
6

为什么滑动窗口技术比查找最大元素的所有其他方法都更好？

滑动窗口最大值技术是一种用于查找数组中给定大小的每个窗口中的最大元素的有用算法。它通常用于必须处理流式数据并在每一步查找固定大小窗口中最大元素的应用中。

滑动窗口最大值技术可能比查找最大元素的所有其他方法更好的一个原因是，它可以使用简单的嵌套循环方法实现，该方法的 time complexity 为 O(nk)，其中 n 是数组的大小，k 是窗口的大小。与其他方法相比，这相对有效，例如对数组进行排序并查找最大元素，其 time complexity 为 O(nlogn)。

滑动窗口最大值技术可能更好的另一个原因是，它可以轻松修改以使用堆等数据结构来跟踪每个窗口中的最大元素，从而将 time complexity 降低到 O(nlogk)。这可能比查找大型数组中最大元素的所有其他方法更有效，特别是如果窗口的大小远小于数组的大小。

总而言之，滑动窗口最大值技术是一种有用且高效的算法，用于查找数组中给定大小的每个窗口中的最大元素。