具有max函数的std :: stack <int>？

如何stack使用max函数实现max,其中max函数的复杂度为O(1)并且它使用O(n)额外内存？

我们的想法是通过堆栈中的对使用来跟踪最大值.如果在堆栈中插入内容,则相应地更新最大值.

class Stack {
private: 
    stack> s;

public:
    bool empty() const {
        return s.empty();
    }

    int max() const {
        assert (empty() == false);
        return s.top().second;
    }

    int pop() {
        int ans = s.top().first;
        s.pop();
        return ans;
    }

    void push(int x) {
        if (s.empty() || x > s.top().second)
        {
            s.emplace(x, x);
        }
        else
        {
            s.emplace(x, s.top().second);
        }
    }
};