您好,登錄后才能下訂單哦!
題目:
定義棧的數(shù)據(jù)結(jié)構(gòu),請在該類型中實現(xiàn)一個能夠得到棧最小元素的min函數(shù)。
思路一:
通過每次在壓入棧頂?shù)脑嘏c當(dāng)前最小元素相比后,保存一遍最小元素,每次彈出,都彈出兩個,這個就能得到棧當(dāng)前最小元素了
代碼:
class Solution { public: void push(int value) { if(s1.size()==0) { s1.push(value); int min=value; s1.push(min); } else { int min=s1.top(); if(value<min) { min=value; } s1.push(value); s1.push(min); } } //彈出兩次 void pop() { int min=s1.top(); s1.pop(); int val=s1.top(); s1.pop(); } int top(){ int min=s1.top(); s1.pop(); int val=s1.top(); s1.push(min); return val; } int min() { return s1.top(); } private: stack<int> s1; };
思路二:利用兩個棧,一個棧用于壓入數(shù)據(jù),另一個棧用于壓入數(shù)據(jù)時的最小元素。無論最小元素是不是壓棧的元素,都保存到第二個棧中
代碼:
class Solution { public: void push(int value) { if(s1.size()==0) { s1.push(value); s2.push(value); } else { s1.push(value); int min=s2.top(); if(min>value) { s2.push(value); } else { s2.push(min); } } } void pop() { if(!s1.empty()) { s1.pop(); s2.pop(); } } int top() { return s1.top(); } int min() { return s2.top(); } private: stack<int> s1,s2; };
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。