Posted on 2008-02-17 11:23
Wang Jinbo 閱讀(4124)
評(píng)論(9) 編輯 收藏 引用 所屬分類(lèi):
算法與數(shù)學(xué)
題目：對(duì)現(xiàn)在的Stack（棧）數(shù)據(jù)結(jié)構(gòu)進(jìn)行改進(jìn)，加一個(gè)min()功能，使之能在常數(shù)，即O(1)時(shí)間內(nèi)給出棧中的最小值。可對(duì)push()和pop()函數(shù)進(jìn)行修改，但要求其時(shí)間復(fù)雜度都只能是O(1)。
題目是在
http://akalius.javaeye.com/blog/162156看到的，提供了兩種方法。不幸的是第一種方法是錯(cuò)誤的，第二種方法也不完全正確。都沒(méi)有考慮到連續(xù)壓入、彈出和有相同元素的情況。我用的方法是基于第一種的，即在push操作前先將要壓入的數(shù)值和當(dāng)前棧中的最小值“打包”成一個(gè)結(jié)點(diǎn)再壓入，如果棧為空，則和自身一起打包。這樣在彈出一個(gè)元素后，棧中的最小元素可直接由彈出的結(jié)點(diǎn)獲得。
其實(shí)這個(gè)算法寫(xiě)起來(lái)很簡(jiǎn)單，我順便復(fù)習(xí)了一下C++的模板方面的東西。C++平時(shí)用得不多，模板這玩意兒更不常用，以至于發(fā)現(xiàn)手生多了。
#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;
}
手生多了，這么點(diǎn)兒東西寫(xiě)了有20分鐘。我測(cè)試了幾組數(shù)據(jù)，應(yīng)該沒(méi)什么問(wèn)題。在JavaEye上有些朋友提到了最小堆，但難以實(shí)現(xiàn)push和pop的O(1)操作。其實(shí)根本沒(méi)有必要，有些問(wèn)題看似很難，很多時(shí)候是我們想復(fù)雜了。