正文
30 包含min函数的栈（举例让抽象问题具体化）
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
题目描述：
定义栈的数据结构（push/pop），请在该类型中实现一个能够得到栈中所含最小元素的min函数（三者的时间复杂度都应为O（1））。
测试用例：
1）新压入栈的数字比之前的最小值大/小
2）弹出的数字不是最小的元素/是最小的元素
解题思路：
1）借助辅助栈存储最小值，辅助栈顶一定都当前栈的最小值
class Solution {
public:
void push(int value) {
if(data.empty()){
data.push(value);
minValue.push(value); // 是一样的A
}else{ //不为空的时候要寻找最小值，添加到辅助栈中
data.push(value);
if(value<minValue.top())
minValue.push(value); // 是一样的A
else
minValue.push(minValue.top());
}
/*
比较简单的判断方法
data.push(value);
if(data.empty() || value<minValue.top()){
minValue.push(value);
}else{
minValue.push(minValue.top());
}
*/
}
void pop() { //既要删除数据栈的栈顶元素，也要删除辅助栈的栈顶元素
//assert(data.size()>0 && minValue.size()>0);
if(data.empty())
return;
data.pop();//用判断栈为空么？？
minValue.pop();
}
int top() { //访问数据栈顶
return data.top();
}
int min() { //访问辅助栈顶 考虑栈为空的时候
//assert(data.size()>0 && minValue.size()>0);
if(data.empty())
return; //实际上应该报错
return minValue.top();
}
private:
stack<int> data;
stack<int> minValue;
};
2）使用key-value对存储
class Solution {
typedef pair<int, int> pii;
stack<pii> s;
public:
void push(int value) {
s.push(pii(value, ::min(value, s.empty() ? value : min()) )); //min()是自己定义的函数s.top().second;
}
void pop() {
s.pop();
}
int top() {
return s.top().first;
}
int min() {
return s.top().second;
}
};
