我遇到了这个问题: 实现一个队列,其中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)的运行时间.有一个更好的方法吗？