c - 在堆栈中查找最小值，时间复杂度为 O(1)

Question

这个问题已经有答案了:

Retrieving the Min element in a stack in O(1) Time (3 个回答)

已关闭 9 年前。

如何以 O(1) 复杂度查找堆栈中的最小值。为了查找堆栈的最小值，我找到了两种方法:1) min = 栈顶值遍历栈并更新min值，得到栈的最小值。这需要 O(N) 复杂度，其中 N 是堆栈中元素的数量

2) 将栈元素放入最小堆中将提取的根值将是堆栈中的最小值这需要 O(N log(N))

但是我如何实现 O(1) 算法，一种独立于输入大小的算法。

这里假设堆栈已经加载了元素

Answer 1

你不能。用于查找任意堆栈的最小元素的 O(1) 算法也可用于查找双向链表的最小元素，然后您可以使用它来创建 O(n) 排序算法。

现在，可以实现一个堆栈，在构建时跟踪其最小元素。然后，这样的堆栈可以返回其存储的最小值，并且如果您碰巧弹出最小元素，则只需执行 O(n) 搜索。但这实际上并不是一回事。