我刚被问到与A公司的面试问题，如下所示:
问题:设计一个数据结构，您可以在其中进行3个操作，即插入，弹出并找到最小值。您应该在固定时间内执行所有这3个操作。
我的回答:我将使用一个链表，在该链表中，我可以在固定时间内进行插入和删除操作，并且我将使用额外的内存来存储最小值。
他提出了第二个问题，说，如果您弹出最低限度，怎么找到第二最低限度？同样，在恒定的时间。
你会告诉他什么？
最佳答案
如果您像上面说的那样做一个链表，又存储了当前的最小值，该怎么办。当您添加新数字时，它将查看前一个最小值，如果当前值较低，则将当前最小值更改为当前值。
例如，假设您有数据:3、6、4、2、7、1。那么列表就是这样
值|分钟
3 | 3-> 6 | 3-> 4 | 3-> 2 | 2-> 7 | 2-> 1 | 1
在您添加/删除项目时，它会记录分钟数。
编辑:
我提到往回走，可能是这样的:
1 | 1-> 7 | 2-> 2 | 2-> 4 | 3-> 6 | 3-> 3 | 3
然后，您将不需要“页脚”。
关于algorithm - 自定义数据结构，用于推送，弹出和查找最小值，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/6103287/