要求
定義棧的數據結構，要求添加一個min 函數，能夠得到棧的最小元素。?
要求函數min、push 以及pop 的時間復雜度都是O(1)。
解法1：
?
使用一個輔助棧來保存最小元素，這個解法簡單不失優雅。設該輔助棧名字為minimum stack，其棧頂元素為當前棧中的最小元素。這意味著
?
- 要獲取當前棧中最小元素，只需要返回minimum stack的棧頂元素即可。
- 每次執行push操作，檢查push的元素是否小于或等于minimum stack棧頂元素。如果是，則也push該元素到minimum?stack中。
- 當執行pop操作的時候，檢查pop的元素是否與當前最小值相等。如果相同，則需要將改元素從minimum?stack中pop出去。
struct minStack{
stack<int> s;
stack<int> minS;
void push(int i){
if (s.empty() || minS.empty()){
s.push(i);
minS.push(i);
}else{
if (minS.top() >= i){
minS.push(i);
}
s.push(i);
}
}
void pop(){
if (s.empty() || minS.empty()){
return;
}
if (s.top() > minS.top()){
s.pop();
}else{
s.pop();
minS.pop();
}
}
int min(){
if (minS.empty())
return -1;
else
return minS.top();
}
};
?
2.巧妙解法
?
另外一種解法利用存儲差值而不需要輔助棧，方法比較巧妙。其中需要說明的幾點：
push(int elem)函數在棧中壓入當前元素與當前棧中最小元素的差值，然后通過比較當前元素與當前棧中最小元素大小，并將它們中間的較小值壓入。
pop()函數執行的時候，先pop出棧頂的兩個值，這兩個值分別是當前棧中最小值min和最后壓入的元素與棧中最小值的差值diff。如果diff<0，則表示最后壓入棧的元素是最小的元素，因此只需將min-diff壓入棧中，并將min值返回即可。min-diff就是當前元素彈出后，棧中剩下元素的最小值。而如果diff>=0且棧不為空，則表示當前值不是最小值，所以需要在棧中壓入最小值min并將diff+min返回；如果棧為空，則表示已經是最后一個數字，直接返回min即可。
?
struct minStackLessSpace{
void push(int i){
if (s.empty()){
s.push(i);
s.push(i);
}
if (i - s.top() < 0){
s.pop();
s.push(i-s.top());
s.push(i);
}else{
int j = s.top();
s.pop();
s.push(i);
s.push(j);
}
}
bool pop(){
if (s.empty())
return false;
int i = s.top();
s.pop();
if (s.top() < 0){
int j = s.top();
s.pop();
s.push(i - j);
}else{
s.pop();
s.push(i);
}
}
stack<int> s;
};
參考：
?
http://blog.csdn.net/ssjhust123/article/details/7752878
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
