20. 包含min函數(shù)的棧
題目描述
定義棧的數(shù)據(jù)結(jié)構(gòu)骗奖，請(qǐng)?jiān)谠擃愋椭袑?shí)現(xiàn)一個(gè)能夠得到棧中所含最小元素的min函數(shù)（時(shí)間復(fù)雜度應(yīng)為O（1））嫩舟。
解題思路：
這道題我們需要?jiǎng)?chuàng)建兩個(gè)棧，一個(gè)棧base來(lái)作為棧結(jié)構(gòu)主體叛复，個(gè)輔助棧sMin來(lái)記錄入棧的最小值仔引，根據(jù)題目接口，我們需要實(shí)現(xiàn)四個(gè)方法：
- void push(int value): 在每次入棧時(shí)褐奥，如果入棧值
value小于sMin中的元素咖耘，則將value壓棧到sMin，這樣能夠保證最小元素永遠(yuǎn)在sMin棧頂 - void pop(): 如果出棧元素等于
sMin棧頂元素時(shí)撬码，sMin棧頂元素出棧 - int top(): 返回棧
base的棧頂元素 - int min(): 返回棧
sMin的棧頂元素
筆者展示的代碼只是簡(jiǎn)單的實(shí)現(xiàn)了題目要求的包含min函數(shù)的棧儿倒，并且通過(guò)了牛客網(wǎng)的測(cè)試用例呜笑。不過(guò)代碼并不完整夫否，比如在調(diào)用pop()方法時(shí)應(yīng)該去判斷base和sMin是否為空，如果為空應(yīng)該拋出異常蹈垢。有興趣的讀者可以進(jìn)一步完善代碼慷吊。
解答：
class Solution {
public:
void push(int value) {
base.push(value);
if(sMin.empty())
sMin.push(value);
if(value < sMin.top())
{
sMin.push(value);
}
}
void pop() {
if(base.top() == sMin.top())
sMin.pop();
base.pop();
}
int top() {
if(!base.empty())
return base.top();
else
return 0x7fffffff;
}
int min() {
if(!sMin.empty())
return sMin.top();
else
return 0x7fffffff;
}
private:
stack<int> base, sMin;
};
大家有興趣可以訪問(wèn)我的個(gè)人博客，不定時(shí)更新一些內(nèi)容哦曹抬！
圖片來(lái)自必應(yīng)壁紙
