4

我有一个具有最大元素的整数列表，我需要跟踪列表中的最大元素：

[3, 1, 2] (3 is the max)

每个时间段，我都会得到一个新的随机元素，将其添加到列表的末尾，并在恒定时间内删除列表的第一个元素。所以，在当前时间段结束时，我的列表会变成这样：

    [3, 1, 2]      (3 is the max)
->  [3, 1, 2, -5]  (don't care about max at this moment)
->  [1, 2, -5]     (now 2 is the max)

我可以保留一个优先级队列，以列表中的值为键，进行 O(log(n)) 插入和删除，但我想知道是否有更有效的（可能 [摊销] 恒定时间？）方法来做到这一点。

4

2 回答 2

1

有 O(1) 摊销复杂度的算法：

使用双端队列： 移动窗口的最小/最大值可以在 O(N) 中实现吗？

有两个堆栈： 实现一个队列，其中 push_rear()、pop_front() 和 get_min() 都是常数时间操作

于 2013-04-12T12:59:05.533 回答
0

案例：

  1. New >= CurrentMax 并且首先：CurrentMax 更新为 New；
  2. New < CurrentMax 和 First < Current Max：不变；
  3. New < CurrentMax and First >= Current Max：搜索确定新的CurrentMax；

然而：

为了使第 3 种情况高效，您需要按插入顺序维护元素的（双向链接）列表，并按大小顺序维护树。然后您只需在列表和树中执行插入/删除，并从树中读取新的当前最大值。这与您的树实现一样高效，O(N) 构建插入顺序列表，O(N log N) 构建排名树。

保存列表元素的数据结构如下所示：

public class Element {
  Element PrevInsertionOrder;
  Element NextInsertionOrder;
  Element RankingTreeParent;
  Element RankingTreeLeftChild;
  Element RankingTreeRightChild;
  int Data;
}

更新：

通过维护具有出现计数的不同键值的第二个（双向链接）列表（而不是上面的第二个树），执行 MAX 确定的 O(1) 时间似乎是可能的。

于 2013-04-12T01:26:30.280 回答