12. 带最小值操作的栈

12. 带最小值操作的栈

• 描述
• 笔记
• 数据
• 评测

实现一个带有取最小值min方法的栈，min方法将返回当前栈中的最小值。

你实现的栈将支持push，pop 和 min 操作，所有操作要求都在O(1)时间内完成。

注意事项

如果堆栈中没有数字则不能进行min方法的调用

样例

如下操作：push(1)，pop()，push(2)，push(3)，min()， push(1)，min() 返回 1，2，1

标签

相关题目
思路：
用两个栈来实现，一个存取数据，另一个存取最小值。如遇比之前_min.top()还小的就push更新_min栈。

class MinStack {
private:
    stack<int> _min;
    stack<int> _data;
    
public:
    /** initialize your data structure here. */
    MinStack() {
        
    }
    
    void push(int x) {
        _data.push(x);
        if(_min.empty()){
            _min.push(x);
        }
        else{
            if(x>_min.top()){
                x=_min.top();
            }
            _min.push(x);
        }
    }
    
    void pop() {
        _data.pop();
        _min.pop();
    }
    
    int top() {
        return _data.top();
    }
    
    int getMin() {
        return _min.top();
    }
};