给定一个包含 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
我通过跟踪窗口每个点的最大元素来解决这个问题，但是当最大元素滑出窗口时遇到了问题。那时，我想不出一种快速的方法来找出最大的剩余元素是什么。
有谁知道解决这个问题的有效算法？
这个老问题 https://stackoverflow.com/questions/4802038/implement-a-queue-in-which-push-rear-pop-front-and-get-min-are-all-constan/4802327#4802327讨论如何在 O(1) 时间内构建支持插入、出列和查找最小值的队列数据结构。请注意，这是not标准优先级队列，而是一个在任何时候都可以在 O(1) 时间内找到它包含的最小元素的值的队列。您可以轻松修改此结构以支持 O(1) 中的 find-max 而不是 find-min，因为这与这个特定问题更相关。
使用这个结构，你可以在 O(n) 时间内解决这个问题，如下所示：
- 将数组的前 k 个元素放入特殊队列中。
- For each element in the rest of the array:
- 使用队列的 find-max 操作报告当前子范围的最大元素。
- 将一个元素从队列中出列，保留旧范围的最后 k-1 个元素。
- 将序列中的下一个元素加入队列，使队列现在保存序列的下一个 k 元素子范围。
这总共需要 O(n) 时间，因为您访问每个数组元素一次，每个元素最多入队和出队一次，并且调用 find-max 恰好 n-k 次。我认为这很酷，因为复杂性是独立于 k，这最初看起来并不一定是可能的。
希望这可以帮助！感谢您提出一个很酷的问题！
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
