Q002_dploop_solution

[rbee3u]

Question_ID: Q002

Language: C++

Time Cost: 25-mins

Time Complexity: O(1)

Solution

首先是构造一个MaxStack(维护最大值的栈)，再用两个栈模拟一个队列。

My Code

#include <algorithm>
#include <stack>
#include <string>
#include <iostream>

class MaxStack {
public:
     MaxStack() {}
    ~MaxStack() {}
    bool empty() {
        return m_stk.empty();
    }
    void push(int x) {
        m_stk.push(x); int y = x;
        if (!m_max.empty()) {
            y = m_max.top();
        }
        m_max.push(std::max(x, y));
    }
    int pop() {
        int z = -1;
        if (!m_stk.empty()) {
            z = m_stk.top();
            m_stk.pop();
            m_max.pop();
        }
        return z;
    }
    int get_max() {
        int z = -1;
        if (!m_max.empty()) {
            z = m_max.top();
        }
        return z;
    }
private:
    std::stack<int> m_stk;
    std::stack<int> m_max;
};

class MaxQueue {
public:
     MaxQueue() {}
    ~MaxQueue() {}
    bool empty() {
        return m_in.empty() && m_out.empty();
    }
    void push(int x) {
        m_in.push(x);
    }
    int pop() {
        if (m_out.empty()) {
            while (!m_in.empty()) {
                m_out.push(m_in.pop());
            }
        }
        return m_out.pop();
    }
    int get_max() {
        return std::max(m_in.get_max()
                     , m_out.get_max());
    }

private:
    MaxStack m_in;
    MaxStack m_out;
};

int main() {
    MaxQueue q; std::string cmd; int x;
    while (std::cin >> cmd) {
        if (cmd == "push") {
            std::cin >> x; q.push(x);
            std::cout << "None" << std::endl;
        } else if (cmd == "pop") {
            std::cout << q.pop() << std::endl;
        } else {
            std::cout << q.get_max() << std::endl;
        }
    }
    return 0;
}

Other

代码看起来比较长，思想其实很简单，核心代码实际上就几行。

[rbee3u]

@m75n 的解法比我这更优雅

[isaacpei]

不够优雅. 但是我相信这个解法在面试里面能拿到60分, 面试官一定会问你如果不用俩栈咋办. 但是用已有知识来搭积木解决问题也是很好的~

[rbee3u]

@isaacpei 其实以前做过POJ的Sliding Window，这题其实和它一样，突然想起来，，，