【ACWing】41. 包含min函数的栈

题目地址:

https://www.acwing.com/problem/content/90/

设计一个支持push,pop,top等操作并且可以在 O ( 1 ) O(1) O(1)时间内检索出最小元素的堆栈。
push(x)–将元素x插入栈中
pop()–移除栈顶元素
top()–得到栈顶元素
getMin()–得到栈中最小元素

代码如下:

#include <stack>
using namespace std;

class MinStack {
public:
    stack<int> stk, stk1;
    MinStack() {
        
    }
    
    void push(int x) {
        stk.push(x);
        if (stk1.empty() || x <= stk1.top()) stk1.push(x);
    }
    
    void pop() {
        if (stk.top() == stk1.top()) stk1.pop();
        stk.pop();
    }
    
    int top() {
        return stk.top();
    }
    
    int getMin() {
        return stk1.top();
    }
};

所有操作时间复杂度 O ( 1 ) O(1) O(1)。

上一篇:【工具类】ScheduledExecutorService 定期线程执行池的使用讲解


下一篇:Java源码学习之并发编程-多线程(三)-sleep和wait