题目:定义栈的数据结构,要求添加一个 min 函数,能够得到栈的最小元素。要求函数 min、 push 以及 pop 的时间复杂度都是 O(1)。
分析:这是去年 google 的一道面试题。
我看到这道题目时,第一反应就是每次 push 一个新元素时,将栈里所有逆序元素排序。这样栈顶元
素将是最小元素。但由于不能保证最后 push 进栈的元素最先出栈,这种思路设计的数据结构已经不是一个 栈了。
在栈里添加一个成员变量存放最小元素(或最小元素的位置)。每次 push 一个新元素进栈的时候,
如果该元素比当前的最小元素还要小,则更新最小元素。 乍一看这样思路挺好的。但仔细一想,该思路存在一个重要的问题:如果当前最小元素被 pop 出去,
如何才能得到下一个最小元素?
因此仅仅只添加一个成员变量存放最小元素(或最小元素的位置)是不够的。我们需要一个辅助栈, 每次 push 一个新元素的时候,同时将最小元素(或最小元素的位置,考虑到栈元素的类型可能是复杂的数 据结构,用最小元素的位置将能减少空间消耗)push 到辅助栈中;每次 pop 一个元素出栈的时候,同时 pop
辅助栈。

题目:定义栈的数据结构,要求添加一个 min 函数,能够得到栈的最小元素。要求函数 min、 push 以及 pop 的时间复杂度都是 O(1)。
分析:这是去年 google 的一道面试题。
我看到这道题目时,第一反应就是每次 push 一个新元素时,将栈里所有逆序元素排序。这样栈顶元
素将是最小元素。但由于不能保证最后 push 进栈的元素最先出栈,这种思路设计的数据结构已经不是一个 栈了。
在栈里添加一个成员变量存放最小元素(或最小元素的位置)。每次 push 一个新元素进栈的时候,
如果该元素比当前的最小元素还要小,则更新最小元素。 乍一看这样思路挺好的。但仔细一想,该思路存在一个重要的问题:如果当前最小元素被 pop 出去,
如何才能得到下一个最小元素?
因此仅仅只添加一个成员变量存放最小元素(或最小元素的位置)是不够的。我们需要一个辅助栈, 每次 push 一个新元素的时候,同时将最小元素(或最小元素的位置,考虑到栈元素的类型可能是复杂的数 据结构,用最小元素的位置将能减少空间消耗)push 到辅助栈中;每次 pop 一个元素出栈的时候,同时 pop
辅助栈。