亚马逊采访:敏叠

Question

我最近接受了SDE的亚马逊采访.有人问我设计一个栈做push,pop并min在O(1).
我得到了逻辑并实现了堆栈的推送.在实现新堆栈的推送时,我调用了给定堆栈和最小堆栈的推送,这是新堆栈的一部分.面试官告诉我,我不能这样做,因为推送将是递归调用.我向他解释说,我们可以用不同的名字命名,但他坚持认为旧堆栈和新堆栈上的操作都称为推送.

我怎么能达到同样的目的？(面试官似乎非常卑鄙,因为我的逻辑是正确的,他仍然告诉我,由于上述原因,我做错了)

Answer 1

实现此目的的一种方法是跟踪堆栈中某些元素下面的所有值的最小值.
对于堆栈中的每个元素,您实际上将拥有2个元素.一个具有实际值,并且在其上方,是其下面所有元素的最小值.

1. 推 - 将新值与最小值进行比较,同时推送值和当前最小值.
2. Pop - 从堆栈中弹出两次(值和当前最小值).
3. 最小 - 返回堆栈顶部.

示例:对于元素7, 9, 3, 5, 1, 2(按此顺序),堆栈将为:

TOP:    1 <--- min(7,9,3,5,1,2)
        2
        1 <--- min(7,9,3,5,1)
        1
        3 <--- min(7,9,3,5)
        5
        3 <--- min(7,9,3)
        3
        7 <--- min(7,9)
        9
        7 <--- min(7)
        7