题目描述 牛客网

• 定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数
• 在该栈中，调用 min、push、pop 的时间复杂度都是 O(1)

题目解读

• 剑指Offer 165

代码

#include<iostream>
#include<stack>
using namespace std;

class Solution {
public:

   void push(int value) {
        stack1.push(value);    
        if(stack2.empty() || value < stack2.top()){ //堆栈为空则返回真
            stack2.push(value);
        }
        else{
            stack2.push(stack2.top());
        }
    }

    void pop() {
        if(! stack1.empty()){
            stack1.pop();
            stack2.pop();
        }
    }

    int top() {
        return stack1.top();
    }

    int min() {
        return stack2.top();
    }

private:
    stack<int> stack1;
    stack<int> stack2;
    
};

main(){
    
    Solution ss;
    ss.push(2);
    ss.push(-5);
    ss.push(9);
    ss.push(3);
    ss.push(6);
    cout<<ss.min()<<endl;
}

总结展望

• 和用两个栈实现队列，用两个队列实现栈是同一个类型的题目