題解 | #包含min函數(shù)的棧#
包含min函數(shù)的棧
http://fangfengwang8.cn/practice/4c776177d2c04c2494f2555c9fcc1e49
2022.0807算法第16題包含min函數(shù)的棧
算法要求min的復(fù)雜度為常數(shù)，剛開始想到了用一個變量存儲min，存儲時更新min沒有問題，但是在pop刪除操作時就比較麻煩了。
如果棧頂元素為最小值，刪除之后的最小值就不知道了。
因此需要其他的結(jié)構(gòu)存儲最小值，可以使用一個輔助棧進(jìn)行存儲。
輔助棧里存儲著當(dāng)前棧元素的最小值，push操作一樣，pop時只需要同樣取出輔助棧的元素即可。
也就是以空間換時間的做法。
實現(xiàn)push函數(shù)：
當(dāng)棧為空或者當(dāng)前元素小于最小值時，更新輔助棧的值
否則直接將輔助棧的棧頂元素重復(fù)加入。
void push(int value) {
if(sta.empty()){
min_num.push(value);
}
else{
if(value<min_num.top())
min_num.push(value);
else
min_num.push(min_num.top());
}
sta.push(value);
}
pop函數(shù)、top函數(shù)和min函數(shù)比較簡單，之間對兩個棧進(jìn)行操作就行；
void pop() {
sta.pop();
min_num.pop();
}
int top() {
return sta.top();
}
int min() {
return min_num.top();
}
投遞拼多多集團(tuán)-PDD等公司10個崗位 >
