2008-02-16
全文显示

Google面试题（六）之解答

引用题目：对现在的Stack（栈）数据结构进行改进，加一个min()功能，使之能在常数，即O(1)，时间内给出栈中的最小值。可对push()和pop()函数进行修改，但要求其时间复杂度都只能是O(1)。 题目是在http://akalius.javaeye.com/blog/162156看到的，提供了两种方法。不幸的是第一种方法是错误的，第二种方法也不完全正确。都没有考虑到连续压入、弹出和有相同元素的情况。我用的方法是基于第一种的，即在push操作前先将要压入的数值和当前栈中的最小值“打包”成一个结点再压入，如果栈为空，则和自身一起打包。这样在弹出一个元素后，栈中的最小元素可直接由弹出的结点 ...
ggggqqqqihc
搜索本博客
存档
最新评论