我可以有一个集合，其中平均添加/删除操作为 O(1)(这对于基于哈希表的集合来说是典型的)，而最差的最大/最小值小于 O(n)，可能是 O(log n)(典型的基于树的集合)？
upd嗯，似乎在最简单的情况下，每次最大/最小消失时我都可以重新扫描所有 N 个元素，一般来说它给了我 O(1)。但是我将我的算法应用于股票交易，其中接近最小/最大的变化更有可能，所以我只是不想每次最大或最小消失时都重新扫描所有内容，我需要比完全重新扫描更聪明的东西给出 O(n)。
upd2在我的案例中，集合包含 100-300 个元素。最大/最小元素的变化是很有可能的，因此最大/最小值经常变化。我需要跟踪最大值/最小值。我仍然想要 O(1) 进行添加/删除。
这是一个不可能的结果，在确定性模型中，对于最坏情况的非摊销边界，常数不好，可以比较和散列键，但不能进行其他操作。(是的，这是很多规定。我支持范埃姆德·博阿斯树的推荐。
与比较下限的通常情况一样，这是一个对抗论点。对手的游戏计划是插入许多键，同时有选择地删除算法具有最多信息的键。最终，算法将无法处理对 max() 的调用。
对手决定关键比较，如下所示。与每个键关联的是一个二进制字符串。每个键最初都有一个空字符串。比较两个键时，它们的字符串被最小扩展，以便两者都不是另一个键的前缀，并且根据字典顺序决定比较。例如，使用键 x、y、z，我们可以有：
x < y: string(x) is now 0, string(y) is now 1
x < z: string(z) is now 1
y < z: string(y) is now 10, string(z) is now 11.
设 k 为一次操作进行的关键比较次数的最坏情况上限。每个键比较最多增加两个字符串总长度，因此对于每个最多 3 * n 插入/删除操作的序列，总字符串长度最多为 6 * k * n。如果我们插入 2 * n 个不同的键，只要有一个键的字符串长度至少为 6 * k，就会穿插删除，那么我们最多删除 n 个键，直到一个至少具有 n 个键的集合，其中每个键都有一个短于 6 * k 位的字符串。
将每个键的字符串任意扩展到 6 * k 位。键字符串的 (6 * k) 位前缀是键所属的存储桶。目前，该算法没有关于存储桶中键的相对顺序的信息。有 2 个 ** (6 * k) 桶，我们想象它们按照 (6 * k) 位前缀规定的递增顺序从左到右排列。对于足够大的 n，存在一个具有恒定(取决于 k)键分数的存储桶，并且键数至少是其右侧组合存储桶的 2 * k 倍。删除后面的键，max() 需要线性数量的额外比较来整理出现在拥有最大值的大桶，因为最多一半多一点的所需工作已经由删除完成。
嗯，你知道max/min < CONST，元素都是数字。基于此，您可以获得O(1)插入并O(k+n/k)找到最小/最大1。
有一个大小k数组，数组中的每个元素都将是一个哈希集。插入时，将元素插入到array[floor((x-MIN)/MAX-MIN)*k)](x=MAX 的特殊情况)。假设元素均匀分布，这意味着每个哈希集都有预期数量的n/k元素。
删除时 - 类似地从相关集中删除。
findMax() 现在按如下方式完成：找到集合不为空的最大索引 - 它需要 O(k) 最坏情况，O(n/k)在第一个非空集合中找到最大元素。
找到最佳 k：
我们需要最小化 k+n/k。
d(n+n/k)/dk = 1-n/k^2 = 0
n = k^2
k = sqrt(n)
这使我们O(sqrt(n) + n/sqrt(n)) = O(sqrt(n))平均找到最小值/最大值，插入/删除 O(1)。
由于最大值和最小值的极端变化，您可能需要不时"重置"表，但给定"安全边界" - 我相信在大多数情况下这不会成为问题。
只要确保你的MAX是类似于2*max，并且每次"重置"DS时都会1/2*minMIN。
(1)假设所有元素都来自已知分布。在我的回答中，我假设一个均匀分布 - 所以每个 x，yP(x)=P(y)，但将其修改为任何已知分布相当容易。