剑指 Offer 30. 包含 min 函数的栈

题目描述

思路

用俩个栈维护

代码1

class MinStack {
    
public:
// /** initialize your data structure here. */
// 剑指 Offer 30. 包含 min 函数的栈
// 定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
    stack<int> A, B;
    MinStack() {
    }
    void push(int x) {
    
        A.push(x);
        if(B.empty() || B.top() >= x) {
    
            B.push(x);
        }
    }
    
    void pop() {
    
        if(A.top() == B.top()) {
    
            A.pop();
            B.pop();
        } else {
    
            A.pop();
        }
    }
    
    int top() {
     
        return A.top();
    }
    
    int min() {
    
        return B.top();
    }
};

/** * Your MinStack object will be instantiated and called as such: * MinStack* obj = new MinStack(); * obj->push(x); * obj->pop(); * int param_3 = obj->top(); * int param_4 = obj->min(); */

感谢阅读