Q002_ryanorz_solution - Githubissues

ryanorz commented 6 years ago

Question_ID: Q002

Language: c++

Time Cost: 60-mins

Time Complexity: O(1)

Solution

My Code

#include <list>
#include <iostream>

using namespace std;

class MyQueue {
private:
    list<int> maxList; // 队头保存最大值，队尾保存除比比前面元素外的最大值
    list<int> nums;    // 使用链表存储队列
public:
    void push(int x);
    int pop();
    int getMax();
};

void MyQueue::push(int x) {
    nums.push_back(x);
    // 丢弃之前的比当前元素小的值
    while (!maxList.empty() && maxList.back() < x) {
        maxList.pop_back();
    }
    maxList.push_back(x);
}

int MyQueue::pop() {
    if (nums.empty()) throw exception();
    int x = nums.front();
    nums.pop_front();
    if (x == maxList.front()) {
        maxList.pop_front();
    }
    return x;
}

int MyQueue::getMax() {
    if (!nums.empty()) {
        return maxList.front();
    } else {
        throw exception();
    }
}

Other

照抄m75n的算法

isaacpei commented 6 years ago

其实我只是想了解一下时间花费在哪了

ryanorz commented 6 years ago

@isaacpei 开始考虑了各种方法，最后都没满意，最后把还Pop会出现o(n)的版本放上去了。使用list时没考虑过把小数追加到后面去，这里思路卡住了。