Posted on 2008-02-17 11:23
Wang Jinbo 阅读(1844)
评论(8) 编辑 收藏 引用 所属分类:
算法与数学
题目：对现在的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分钟。我测试了几组数据，应该没什么问题。在JavaEye上有些朋友提到了最小堆，但难以实现push和pop的O(1)操作。其实根本没有必要，有些问题看似很难，很多时候是我们想复杂了。