20. 包含min函数的栈
题目描述
定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。
解题思路：
这道题我们需要创建两个栈，一个栈base来作为栈结构主体，个辅助栈sMin来记录入栈的最小值，根据题目接口，我们需要实现四个方法：
- void push(int value): 在每次入栈时，如果入栈值
value小于sMin中的元素，则将value压栈到sMin，这样能够保证最小元素永远在sMin栈顶 - void pop(): 如果出栈元素等于
sMin栈顶元素时，sMin栈顶元素出栈 - int top(): 返回栈
base的栈顶元素 - int min(): 返回栈
sMin的栈顶元素
笔者展示的代码只是简单的实现了题目要求的包含min函数的栈，并且通过了牛客网的测试用例。不过代码并不完整，比如在调用pop()方法时应该去判断base和sMin是否为空，如果为空应该抛出异常。有兴趣的读者可以进一步完善代码。
解答：
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;
};
大家有兴趣可以访问我的个人博客，不定时更新一些内容哦！
图片来自必应壁纸
