letcode::最小栈

最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。

示例 1:
输入：
[“MinStack”,“push”,“push”,“push”,“getMin”,“pop”,“top”,“getMin”]
[[],[-2],[0],[-3],[],[],[],[]]
输出：
[null,null,null,null,-3,null,0,-2]
解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.

思路

定义_min成员，记录栈中最小元素（不行）
可以定义一个_min成员，每次栈插入数据时，就更新_min。
但是如果栈删除的数据恰好是当前栈中最小的数据，_min的更新就很困难，且不论栈不允许遍历，遍历的O(N)复杂度是与题意“在常数时间内检索到最小元素的栈”相悖的。

用一个栈记录栈中最小元素
定义两个栈：_st、_minst。
_st用于正常插入、删除数据。
_minst与_st同步插入、删除，但是_minst插入、删除的数据是当前_st中的最小值。（这样做，_minst栈顶的元素即为_st中的最小值）
如下，以栈中数据是“3、4、5、1、6、1”为例。
在这里插入图片描述

_minst也可以不与_st时时刻刻同步插入删除。
_minst只需在本身为空、插入的元素小于等于原先的最小值和删除的元素等于当前的最小值时，执行插入、删除操作。
如下，以栈中数据是“3、4、5、1、6、1”为例
在这里插入图片描述

如果将_minst执行插入删除操作的条件中的“插入的元素小于等于原先的最小值”
改为“插入的元素小于原先的最小值”，且恰好下一次的操作是删除栈顶元素时，就会出现错误。
还是以栈中元素是“3、4、5、1、6、1”为例

这时，_minst的栈顶元素明显不是_st中的最小元素了。

代码

class MinStack {
public:
    MinStack() {

    }
    
    void push(int val) {
        _st.push(val);
        if (_minst.empty() || val <= _minst.top())
        {
            _minst.push(val);
        }
    }
    
    void pop() {
        if (_st.top() == _minst.top())
        {
            _minst.pop();
        }

        _st.pop();
    }
    
    int top() {
        return _st.top();
    }
    
    int getMin() {
        return _minst.top();
    }
    private:
    stack<int> _st;//保存栈中元素
    stack<int> _minst;//保存栈中最小值
};