2008-02-16

Google面试题（六）之解答

引用
题目：对现在的Stack（栈）数据结构进行改进，加一个min()功能，使之能在常数，即O(1)，时间内给出栈中的最小值。可对push()和pop()函数进行修改，但要求其时间复杂度都只能是O(1)。

题目是在http://akalius.javaeye.com/blog/162156看到的，提供了两种方法。不幸的是第一种方法是错误的，第二种方法也不完全正确。都没有考虑到连续压入、弹出和有相同元素的情况。我用的方法是基于第一种的，即在push操作前先将要压入的数值和当前栈中的最小值“打包”成一个结点再压入，如果栈为空，则和自身一起打包。这样在弹出一个元素后，栈中的最小元素可直接由弹出的结点获得。
其实这个算法写起来很简单，我顺便复习了一下C++的模板方面的东西。C++平时用得不多，模板这玩意儿更不常用，以至于发现手生多了。 
#include <vector>
#include <utility>
using namespace std;

template<class T>
class Stack{
	vector<pair<T,T> > stack;
	T minimum;
public:
	vector<pair<T,T> >& push(T e);
	vector<pair<T,T> >& pop();
	T min();
};
template<class T>
vector<pair<T,T> >& Stack<T>::push(T e){
	if (stack.empty()){
		minimum=e;
	}
	pair<T,T> node(e,minimum);
	stack.push_back(node);
	if (e<minimum){
		minimum=e;
	}
}
template<class T>
vector<pair<T,T> >& Stack<T>::pop(){
	pair<T,T> node=stack.back();
	minimum=node.second;
	stack.pop_back();
}
template<class T>
T Stack<T>::min(){
	return minimum;
}

手生多了，这么点儿东西写了有20分钟。我测试了几组数据，应该没什么问题。

补充：为了练习Ruby，又写了一个Ruby版的，在http://ggggqqqqihc.javaeye.com/blog/162874。
评论
发表评论

您还没有登录，请登录后发表评论

ggggqqqqihc
搜索本博客
存档
最新评论