在一个无限数字集合中，找到最后k个元素中的最小数。

Question

您将获得一个无限的数字列表。在最后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。有人知道如何解决这个问题吗？

- user2731584

---

你能否稍微澄清一下你的问题？或者提供一个例子？ - Mr. Llama

这是关于编程还是数学？如果是关于编程，请展示一下你已经尝试过的内容。如果是关于数学的话，那么它不属于本站的主题，应该移步到http://math.stackexchange.com/。出于好奇，如何在无限列表中存在“最后k个元素”？ - Peter Herdenborg

@Mr.Llama，我已经添加了一个示例，请现在检查。 - user2731584

你可以使用最小堆来实现这个。 - higuaro

那么您真正想要做的是“维护”一个值，这个值是迄今为止最后k个读取项目中最小的数字？ - Jim Mischel

Answer 1

这个问题有一个简单的摊销O(1)算法。

实际上，这个问题是要实现一个大小为k的队列，并且具有（摊销）O(1)访问其最小值的能力。有了这样一个队列，我们可以通过首先使用k个Put操作来填充队列，然后通过在放置新元素之前将最古老的元素移出来来维护队列来处理无限输入。

让我们从一个不同但更简单的问题开始：具有O(1)访问其最小值的堆栈。那很简单。我们只需要保持一组成对的堆栈元素：每个堆栈元素包含一个数据值和该点的最小值。然后，堆栈的最小值是与堆栈顶部元素相关联的最小值。

现在，快速分支一下。如果我们只有一个堆栈类型，如何有效地实现队列数据类型？答案是所谓的“银行家队列”，它使用两个堆栈，我将它们称为“incoming”和“outgoing”。 Put通过简单地推入incoming来实现。 Shift通过弹出outgoing来实现，除非它为空。当outgoing为空时，我们通过依次从incoming中弹出每个元素并将其推入outgoing来重新填充它，这会将incoming翻转到outgoing中。

银行家队列在两个操作中都是摊销O(1)，因为（从长期来看），每个元素都恰好从每个堆栈中推入和弹出一次。这是“摊销”的，因为偶尔会（如果队列是固定大小，则每k个操作）反转一个完整的元素堆栈，但这平均为O(1)。

现在，我们对原始问题有了完整的摊销O(1)解决方案：我们使用具有两个最小堆栈的银行家队列。然后，在任何给定时刻，队列的最小值是两个最小堆栈的最小值之一。

一旦我们有了一般想法，就可以想出几种优化方法。首先，由于我们知道队列的总大小，因此我们可以使用循环缓冲区来包含两个堆栈。我们可以通过将其中一个堆栈存储为反向来避免反转操作（尽管我们仍然需要重新计算堆叠的最小值）。最后，我们可以通过注意到我们实际上不需要一个MinStack来存储incoming - 我们只需要知道它的当前最小值 - 并且我们不需要在outgoing中存储值，我们只需要存储最小值来节省存储空间。

将所有内容组合在一起，得到一个简单的C++实现：

template<typename value_type>
class MinBuffer {
  private:
    std::vector<value_type> queue_;
    value_type incoming_min_;
    int index_;
  public:
    MinBuffer(int capacity)
      : queue_(capacity + 1, std::numeric_limits<value_type>::max()),
        incoming_min_(std::numeric_limits<value_type>::max()),
        index_(0) {
      assert(capacity > 0);
    };
    void push_back(const value_type& val) {
      if (index_ == queue_.size() - 1) {
        while (--index_)
          queue_[index_] = std::min(queue_[index_], queue_[index_ + 1]);
        incoming_min_ = std::numeric_limits<value_type>::max();
      }
      queue_[index_++] = val;
      incoming_min_ = std::min(val, incoming_min_);
    }
    value_type getmin() const {
      return std::min(incoming_min_, queue_[index_]);
    }
};

注：

上述代码使用了最大可能的值类型作为哨兵，这是 Sedgewick 最好的传统；内部队列的最后一个元素始终是哨兵值，它是 min 函数的恒等元素。这样可以节省很多繁琐的检查和特殊情况。

内部队列的前半部分（直到但不包括位置 index_）是 incoming 栈，栈顶位于最高索引处。接下来，直到队列的末尾，是来自 outgoing 栈的最小值，以相反的顺序存储，使得顶部位于 index_。如果 outgoing 为空，则 index_ 为 k，且 queue_[k] 始终是哨兵值。

- rici

Answer 2

您也可以通过维护一个包含元素和它们的索引的deque，以O(1)的平摊时间执行此操作。

当您看到一个新元素时：

- 从左侧删除所有大于它的元素。这些元素不可能再成为最小值：它们比新元素早，且比它大，因此它们总是会被新元素所支配。 - 如果右侧最右边的元素太旧（添加了超过k个元素），则将其删除。所有元素都具有不同的索引，并且每个新元素的索引增加1。因此，每次只有一个元素可能会变得太旧。 - 将新元素添加到左侧。

通过这个维护过程，deque总是按元素从右到左排序（即，最右边的元素是最小的），并按索引从左到右排序（因为新元素从左侧添加）。

因此，最近的最小元素是deque的最右侧元素。

更新：看起来我想出了这个算法：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)，但通常使用的内存要少得多（它不存储太大而永远不会成为最小值的元素）。

- Kolmar

---

这很棒。但我不理解它的工作原理。你能举个例子来解释一下吗？ - user2731584

或者可以提供一个带有Python示例输入的完整程序吗？ - user2731584

@user2731584 或许这篇文章能帮助你整理事情。 - Niklas B.

非常感谢。我会去查看的。 - user2731584

@user2731584 这里是带有一些调试输出的代码，以便查看其工作原理：http://ideone.com/DB4Bfn - Kolmar

Answer 3

请查看笛卡尔树 (Cartesian tree)。每个节点有两个键：第一个键是二叉搜索树的键，第二个键是堆的键。您可以使用第一个键来存储元素的编号，第二个键来存储元素的值。您将能够在 O(log(k)) 时间内添加新元素，在 O(log(k)) 时间内删除旧元素，并在常数时间内获得具有最小值的元素。

- Aleksei Shestakov

---

如果element's number是元素索引（我猜测是这样，因为另一个键是elements's value），它最终会溢出，因为序列是无限的。 - fjardon

@Kolmar 是的，我看过了 :) 但是当你溢出时会发生什么？你将使用哪个元素的编号？它将如何与旧元素进行比较？ - fjardon

@fjardon 这是一个搜索树的第一个索引，所以你可以找到并删除元素（current_number - k）（你可以跟踪current_number）。 - Kolmar

@fjardon 那么你就不需要删除任何东西。这只会发生在列表的前k个元素中，在那之后，树中总是恰好有k个元素。 - Kolmar

@fjardon 您关于溢出的观点是正确的。我建议使用 index % k 作为第一个键，这样就不会发生溢出了。 - Aleksei Shestakov

Answer 4

你可以实现一个混合结构，介于最小堆和链表之间。每个堆元素都有一个指向下一个元素的链接。你保留头部和尾部。你在尾部添加元素，并同时从堆中移除头部元素。

每个元素将在 O(log k) 时间内处理。

以下是 Python 示例：

输出：

Pushed:  2, Popped: None, Minimum (last 3):  2
Pushed:  1, Popped: None, Minimum (last 3):  1
Pushed:  3, Popped: None, Minimum (last 3):  1
Pushed:  4, Popped:    2, Minimum (last 3):  1
Pushed:  2, Popped:    1, Minimum (last 3):  2
Pushed: -4, Popped:    3, Minimum (last 3): -4
Pushed:  3, Popped:    4, Minimum (last 3): -4

代码：

class Node:
    def __init__(self, value, index, next):
        self.value = value
        self.index = index
        self.next = next

class LinkedHeap:
    def __init__(self):
        self.V = []
        self.head = self.tail = Node(None, -1, None)

    def count(self):
        return len(self.V)

    def minimum(self):
        return (self.V[0].value if self.count() > 0 else None)

    def push(self, value):
        node = Node(value, len(self.V), None)
        self.tail.next = node
        self.tail = node

        self.V.append(node)
        self.bubble_up(len(self.V)-1)

    def pop(self):
        if not len(self.V): return None

        node = self.head.next
        self.head.next = node.next

        self.V[node.index] = self.V[-1]
        self.V[node.index].index = node.index
        self.V.pop()
        self.bubble_down(node.index)
        return node.value

    def bubble_up(self, n):
        while n != 0 and self.less(n, (n-1)/2):
            self.swap(n, (n-1)/2)
            n = (n-1)/2

    def bubble_down(self, n):
        while self.less(n*2+1, n) or self.less(n*2+2, n):
            c = self.min(n*2+1, n*2+2)
            self.swap(n, c)
            n = c

    def less(self, a, b):
        if a>=self.count(): return False
        if b>=self.count(): return True
        return self.V[a].value<self.V[b].value

    def min(self, a, b):
        return (a if self.less(a,b) else b)

    def swap(self, a, b):
        self.V[a], self.V[b] = self.V[b], self.V[a]
        self.V[a].index = a
        self.V[b].index = b


L = [2, 1, 3, 4, 2, -4, 3]

T = LinkedHeap()

for number in L:
    T.push(number)
    popped = T.pop() if T.count() > 3 else None
    if T.count() > 3:
        T.pop()
    print 'Pushed: {:2}, Popped: {:4}, Minimum (last 3): {:2}'.format(number, popped, T.minimum())

- Juan Lopes

---

这如何解决查找最小值问题？我打算使用循环数组来保存这些值。然后呢？ - user2731584

堆仍将存储在数组中，第一个元素将是最小值。我将在Python中实现一个示例。 - Juan Lopes

谢谢你的代码。我想这个问题不能比O(log k)更好地解决了 :) - user2731584

Answer 5

只需使用大小为K的MaxHeap。如果您看到任何小于最大元素的元素，请删除根并插入新元素。

获取元素的运行时间为k log n（需要从堆中删除所有元素）。插入时间为log n。

- Sandeep