1. 题目描述
题目链接：155. 最小栈
2. 解题思路
借用一个辅助栈 _minst，用于存获取 stack 中最小值。
算法流程：
-
push() 方法： 每当
push()新值进来时，如果 小于等于_minst栈顶值，则一起push()到_minst，即更新了栈顶最小值； -
pop() 方法： 判断将
pop()出去的元素值是否是_minst栈顶元素值（即最小值），如果是则将_minst栈顶元素一起pop()，这样可以保证_minst栈顶元素始终是 tack 中的最小值。 -
getMin() 方法： 返回
_minst栈顶即可。
_minst 作用分析：
-
_minst等价于遍历 stack 所有元素，把升序的数字都删除掉，留下一个从栈底到栈顶降序的栈。 -
相当于给 stack 中的降序元素做了标记，每当
pop()这些降序元素，_minst会将相应的栈顶元素pop()出去，保证其栈顶元素始终是 stack 中的最小元素。
复杂度分析：
- 时间复杂度
O
(
1
)
O(1)
O(1)：压栈，出栈，获取最小值的时间复杂度都为O
(
1
)
O(1)
O(1) 。 - 空间复杂度
O
(
N
)
O(N)
O(N)：包含 N 个元素辅助栈占用线性大小的额外空间。
3. 动图演示
看一个动图
4. 代码实现
代码示例
class MinStack {
public:
// 不需要写构造函数，因为是自定义类型，会调用默认的构造函数
MinStack()
{}
void push(int val) {
_st.push(val);
// 1.当minst为空，也就是第一次的时候，入元素
// 2.当minst的栈顶元素小于等于val，那么就入元素
if (_minst.empty() || val <= _minst.top()) {
_minst.push(val);
}
}
void pop() {
// st的栈顶元素如果等于minst的栈顶元素, 那么就pop掉minst的元素
if (_st.top() == _minst.top()) {
_minst.pop();
}
// 否则直接pop掉st的栈顶元素
_st.pop();
}
int top() {
return _st.top();
}
int getMin() {
return _minst.top();
}
private:
stack<int> _st;
stack<int> _minst;
};
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/80825.html
