在O(1)中实现堆栈(push，pop和findmin) [英] Implement stack (push, pop and findmin) in O(1)
问题描述
我已经看到了此问题的两个堆栈实现，但是我真的很困惑，因为它如何获得O(1)操作. 考虑以下示例:
I have already seen two stack implementation of this question but I am really confused as how one could get O(1) operation. consider following example:
S1[3542761986759]
S2[3332221111111]
这里的想法/算法是
- 将元素E推到S1上
- 检查S2的顶部是否> = E，如果为true，则在S2上插入E
但是，当调用getMin时，我们返回S2的顶部，但由于S2包含重复的当前min元素，因此使S2处于怪异状态，因此解决方案是在S2中搜索下一个最小元素并将其返回.这是O(n).
But when getMin is called, we return top of S2 but that leaves S2 in weird state as S2 contains repeated current min elements, so the solution is to search next minimum element in S2 and return it. This is O(n).
任何人都可以帮助我了解解决方案吗?
Can anyone please help me to understand the solution?
推荐答案
使用链接列表存储当前的最小值.添加新数字时，它会查看前一个最小值，如果当前值较低，则将当前最小值更改为当前值.
Using a linked list store the current minimum value. When you add a new number it looks at the previous min and changes the current min to the current value if the current value is lower.
例如...假设您有数据:3、6、4、2、7、1.那么列表就是这样
E.g... Assume you have the data: 3, 6, 4, 2, 7, 1. Then this is what the list would look like
value | min
value|min
3|3 -> 6|3 -> 4|3 -> 2|2 -> 7|2 -> 1|1
当您推送/弹出项目时，它将跟踪分钟. 当然，您需要有一个根节点和一个指定为页脚"的节点，以便您可以访问O(1)中的末尾.
That'll keep track of the mins as you push/pop items. Granted you'll need to have a root node and a node designated as a "footer" so you can access the end in O(1).
或者您可以倒退它，并在其前面添加内容，并在每次插入时更改根节点……也可以使用.可能是这样的:
Or you could go backwards with it and add things to the front and change the root node every insert... that would work too. It would be something like this:
1|1 -> 7|2 -> 2|2 -> 4|3 -> 6|3 -> 3|3
然后，您将不需要页脚"节点.
Then you wouldn't need the "footer" node.
这两个值都将跟踪当前最小值的推送时间.这样，当实际最小值被推入时，它将知道O(1)中的第二个最小值是什么.
Both of these will keep track of the current min value for when the value was pushed. That way when the actual min value is pushed, it will know what the second min value was in O(1).
这篇关于在O(1)中实现堆栈(push，pop和findmin)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
