algorithm - 亚马逊采访 : Min stack

Question

我最近参加了 SDE 的亚马逊面试。我被要求设计一个在 O(1) 中执行 push、pop 和 min 的堆栈。
我得到了逻辑并实现了堆栈的推送。在实现新堆栈的推送时，我在给定堆栈和最小堆栈上调用了推送，它们是新堆栈的一部分。面试官告诉我，我不能那样做，因为推送将是一个递归调用。我向他解释说，我们可以给它起不同的名字，但他坚持说对旧栈和新栈的操作都叫 push。

我怎样才能达到同样的效果？

Answer 1

实现这一点的一种方法是跟踪堆栈中某个元素下方的所有值的最小值。
对于堆栈中的每个元素，您实际上将拥有 2 个元素。一个是实际值，在它上面是它下面所有元素的最小值。

1. 推送 - 将新值与顶部的最小值进行比较，然后推送该值和当前的最小值。
2. 弹出 - 仅从堆栈中弹出两次(值和当前最小值)。
3. Min - 返回栈顶。

示例:对于元素 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