c++ - std::stack<int> 具有最大功能？

Question

如何实现 stack<int>使用最大操作，最大函数的复杂度为 O(1) 并且它使用 O(n) 额外内存？

Answer 1

想法是通过在堆栈中使用对来跟踪最大值。如果你向堆栈中插入一些东西，你会相应地更新最大值。

class Stack {
private: 
    stack<pair<int,int>> 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);
        }
    }
};