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

发布时间：2020-12-16 03:47:20 所属栏目：百科来源：网络整理

导读：我们给出一个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,最初似乎并不一定是可能的.

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!