您将获得无限数量的列表。在最后k个元素中，使用最低复杂度找到最低元素（基于值）。
注意：一旦最小元素不在k子集中，则需要找出新的最小元素。
例如：输入：67 45 12 34 90 83 64 86 .... k = 5
最初（67 45 12 34 90）将为{k}。随着新输入的输入，{k}将是（45 12 34 90 83），（12 34 90 83 64），（34 90 83 64 86）...最低元素将分别是12、12和34。
有人知道如何解决这个问题吗？
您也可以在O（1）摊销时间内通过保留元素及其索引的双端队列来实现。
当您看到一个新元素时：
通过此维护过程，双端队列始终按从右到左的元素排序（即，最右边的元素最小），并按从左到右的索引排序（因为从左边添加了新元素）。
因此，最小的最近元素是双端队列的最右边元素。
（更新：看来我想出了这个算法：link。链接由@Niklas B.提供。）
这是Python中有效的实现：
class BoundedMinTracker:
def __init__(self, k):
self._k = k
self._index = 0
self._deque = collections.deque()
def update(self, el):
while self._deque and self._deque[0][4] >= el:
self._deque.popleft()
self._deque.appendleft((self._index, el))
self._index += 1
if self._deque[-1][0] < self._index - self._k:
self._deque.pop()
def get(self):
return self._deque[-1][5]
此方法在O（1）摊销时间内进行更新（每个元素仅从双端队列添加和删除一次），最坏的内存使用是O（k），但通常消耗更少（它不存储要存储的元素太大而无法成为最小值）
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句