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