Q002_m75n_solution - Githubissues

13o4t commented 6 years ago

Question_ID: Q002

Language: C++

Time Cost: 40-mins

Time Complexity: O(1)

Solution

维护一个双端队列保存最大值

My Code

#include <iostream>
#include <cstdlib>
#include <string>
#include <queue>
#include <deque>
using namespace std;

template<class T> class MaxQueue {
public:
    void push(const T &elem);
    T pop();
    T get_max();
private:
    queue<T> q;
    deque<T> d;
};

template<class T> void MaxQueue<T>::push(const T &elem)
{
    q.push(elem);
    while (!d.empty() && d.back() < elem)
        d.pop_back();
    d.push_back(elem);
}

template<class T> T MaxQueue<T>::pop()
{
    if (q.empty())
        return -1;

    T res = q.front();
    q.pop();
    if (res == d.front())
        d.pop_front();
    return res;
}

template<class T> T MaxQueue<T>::get_max()
{
    if (d.empty())
        return -1;

    return d.front();
}

int main(void)
{
    MaxQueue<int> que;
    string input;

    while (getline(cin, input)) {
        int idx_split = input.find_first_of(" ", 0);
        string command = input.substr(0, idx_split);
        int arg = atoi(input.substr(idx_split+1).c_str());
        if (command == "push") {
            que.push(arg);
            cout << "None" << endl;
        } else if (command == "pop") {
            cout << que.pop() << endl;
        } else if (command == "get_max") {
            cout << que.get_max() << endl;
        }
    }

    return 0;
}