自定义数据结构,用于推送,弹出和查找最小值

Question

我刚被问到A公司的面试问题如下:

问题: 设计一个数据结构,您可以在其中进行3次操作,推送,弹出并找到最小值.您应该在恒定时间内完成所有3个操作.

我的答案:我会使用链接列表,我可以在恒定时间内插入和删除,我会使用额外的内存来存储最小值.

他想出了第二个问题,如果你弹出最小值,你怎么找到第二个最小值？再次,在不断的时间.

你会告诉他什么？

Answer 1

最小堆栈问题 - http://courses.csail.mit.edu/iap/interview/Hacking_a_Google_Interview_Practice_Questions_Person_A.pdf

来自PDF:

问题:最小堆栈

描述支持"push","pop"和"find minimum"操作的堆栈数据结构."查找最小值"返回堆栈中的最小元素.

好答案:存储两个堆栈,其中一个堆栈包含堆栈中的所有项目,其中一个是最小堆栈.要推动元素,请将其推入第一个堆栈.检查它是否小于第二个堆栈的顶部项目; 如果是这样,将它推到第二个堆栈上.要弹出项目,请从第一个堆栈弹出它.如果它是第二个堆栈的顶部元素,则从第二个堆栈弹出它.要查找最小元素,只需返回第二个堆栈顶部的元素.每个操作需要O(1)时间.

Answer 2

如果你像你说的那样做一个链表怎么办,但也存储当前的最小值.添加新数字时,它会查看前一个最小值,并在当前值较低时将当前最小值更改为当前值.

例如..假设您有数据: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然后你wouln't需要"页脚".