我遇到了这个问题: 实现一个队列,其中push_rear(),pop_front()和get_min()都是常量时间操作.
我最初想过使用一个最小堆数据结构,它对于get_min()具有O(1)复杂度.但是push_rear()和pop_front()将是O(log(n)).
有谁知道实现这样一个有O(1)push(),pop()和min()的队列的最佳方法是什么？
我搜索了这个,并想指出这个算法极客线程.但似乎没有一个解决方案遵循所有3种方法的恒定时间规则:push(),pop()和min().
感谢所有的建议.
给定一个大小为n和k的数组,你如何找到每个大小为k的连续子数组的最大值？
例如
arr = 1 5 2 6 3 1 24 7
k = 3
ans = 5 6 6 6 24 24
我正在考虑使用一个大小为k的数组,每一步都将最后一个元素逐出,并添加新元素并在其中找到最大元素.它导致O(nk)的运行时间.有一个更好的方法吗？
我们给出了一个由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
我通过跟踪每个点上窗口的最大元素来解决问题,但是当最大元素滑出窗口时遇到了问题.那时,我想不出一个快速的方法来弄清楚剩下的最大元素是什么.
有谁知道解决这个问题的有效算法？
最近我陷入了困境.算法部分需要计算长度为K的滑动窗口的最大元素之和.其中K的范围是1 <= K <= N(阵列的N长度).
示例如果我有一个数组A作为5,3,12,4
长度为1的5 + 3 + 12 + 4 = 24
滑动窗口:长度为2的5 + 12 + 12 = 29
滑动窗口:长度为3的12 + 12 = 24
滑动窗口:长度为4的滑动窗口:12
Final answer is 24,29,24,12.
我试过这个O(N ^ 2).对于长度为K的每个滑动窗口,我可以用O(N)计算最大值.由于K高达N.因此,总体复杂度变为O(N ^ 2).
我正在寻找O(N)或O(NlogN)或与此算法类似的东西,因为N可能高达10 ^ 5.
注意:数组中的元素可以大到10 ^ 9,因此输出最终答案为模10 ^ 9 + 7
编辑:我实际上想要找到K的每个值(即从0到N)的答案线性时间或O(NlogN)不在O(KN)或O(KNlogN)中,其中K = {1,2,3,...... N}
是否有特定的算法允许我在小/中型滑动窗口上保持最小/最大(典型大小为600,所有元素都是整数)？窗口实际上是流中的最后N个观察值.所以,我添加了一个新观察并删除了每个时间单位的最老观察,所以我想保持最后和最大值超过最后N个观察点.
这与滑动窗口最小算法中所述的问题不同,因为我不维护整个数据,因此"基于索引"的解决方案在此不适用.此外,我的输入数据本身将是一个圆形数组.
堆可能不会很好地工作:我不删除/弹出Min/Max元素,但是最旧的元素,这将首先破坏堆的目的.
log(n)基于复杂性的结构(如红黑树)可以很好地工作,而splay树可能更适合我所拥有的数据类型,但它们对于我的大小来说有点过分. d处理？