题解 | #包含min函数的栈#
包含min函数的栈
https://www.nowcoder.com/practice/4c776177d2c04c2494f2555c9fcc1e49
class Solution {
public:
void push(int value) {
s1.push(value);
//空或者新元素较小，则入栈
if(s2.empty() || s2.top()>value)
s2.push(value);
else
//重复加入栈顶
s2.push(s2.top());
}
void pop() {
//如果当前s1栈顶是最小元素，则s2栈顶也是最小元素，都要删除
//如果当前s1栈顶不是最小元素，则s2栈顶是重复的最小元素，也要删除，使两个栈的大小保持一致，这样当s1长度为0时，s2也为0，便于对s2进行管理
s1.pop();
s2.pop();
}
int top() {
return s1.top();
}
int min() {
return s2.top();
}
private:
//用于栈的push 与 pop
stack<int> s1;
//用于存储最小min
stack<int> s2;
};
思路：用另外一个栈来存储最小值
我们都知道栈结构的push、pop、top操作都是O(1)，但是min函数做不到，于是想到在push的时候就将最小值记录下来，由于栈先进后出的特殊性，我们可以构造一个单调栈，保证栈内元素都是递增的，栈顶元素就是当前最小的元素。
具体做法：
- step 1：使用一个栈记录进入栈的元素，正常进行push、pop、top操作。
- step 2：使用另一个栈记录每次push进入的最小值。
- step 3：每次push元素的时候与第二个栈的栈顶元素比较，若是较小，则进入第二个栈，若是较大，则第二个栈的栈顶元素再次入栈，因为即便加了一个元素，它依然是最小值。于是，每次访问最小值即访问第二个栈的栈顶。
海康威视公司氛围 306人发布
，
查看19道真题和解析