c – 如何找到给定数组中某些固定给定长度的每个子阵列的最大值

概述我们给出一个n个元素和整数k的数组.假设我们要在数组中滑动长度为k的窗口,报告每个窗口中包含的最大值.例如,给定数组 15 10 9 16 20 14 13 给定一个长度为4的窗口,我们将输出 [15 10 9 16] 20 14 13 ---> Output 16 15 [10 9 16 20] 14 13 ---> Output 20 15 1 我们给出一个n个元素和整数k的数组.假设我们要在数组中滑动长度为k的窗口,报告每个窗口中包含的最大值.例如,给定数组

15  10   9  16  20  14  13

给定一个长度为4的窗口,我们将输出

[15  10   9  16] 20  14  13   ---> Output 16 15 [10   9  16  20] 14  13   ---> Output 20 15  10 [ 9  16  20  14]  13  ---> Output 20 15  10   9 [16  20  14  13]  ---> Output 20

所以结果会是

16  20  20  20

我正在通过跟踪每个窗口的最大元素来处理这个问题,但是当最大的元素从窗口中滑出时遇到问题.在那一点上,我想不出一个快速的方法来找出最大的剩余元素.

有没有人知道一个有效的算法来解决这个问题？

解决方法 This older question讨论如何在O(1)时间内构建支持insert,dequeue和find-min的队列数据结构.请注意,这不是一个标准的优先级队列,而是一个队列,您可以随时在O(1)时间内找到它包含的最小元素的值.您可以轻松地修改此结构,以支持O(1)中的find-max,而不是find-min,因为这与此特定问题更相关.

使用这种结构,可以在O(n)时间内解决这个问题,如下所示：

将阵列的前k个元素排队到特殊队列中.
>对于数组的其余部分的每个元素：

>使用队列的find-max *** 作来报告当前子范围的最大元素.
>从队列中取出一个元素,将旧范围的最后一个k-1元素保留在适当位置.
>从序列中排队下一个元素,导致队列现在保存序列的下一个k元素子范围.

这总共需要O(n)个时间,因为您访问每个数组元素一次,最多一次排队和排队,最后调用find-max n-k次.我认为这是非常酷的,因为复杂性独立于k,最初似乎并不一定是可能的.

希望这可以帮助！谢谢你提出一个很酷的问题！

总结

以上是内存溢出为你收集整理的c – 如何找到给定数组中某些固定给定长度的每个子阵列的最大值全部内容，希望文章能够帮你解决c – 如何找到给定数组中某些固定给定长度的每个子阵列的最大值所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。