Leetcode.155.Min Stack

题目

自己实现一个栈, 需要在一个O(1)复杂度求出栈的最小值.

Output: push(), pop(), int top(), int getMin()

思路

使用map或者vector都可以, vector应该是效率最高的.
最小值有一个特点, 这是一个栈, 如果栈底是最小值, 那无论怎么pop, 栈底都是最小值.
使用数组记录最小值即可, 类似于DP.

class MinStack {
public:

MinStack() {
}
void push(int x) {
    m_stack.push_back(x);
    if (m_min.empty()) {
        m_min.push_back(x);
    } else {
        if (x < m_min.back()) {
            m_min.push_back(x);
        } else {
            m_min.push_back(m_min.back());
        }
    }
}
void pop() {
    m_stack.pop_back();
    m_min.pop_back();
}
int top() {
    return m_stack.back();
}

int getMin() {
    return m_min.back();
}

private:
vector<int> m_stack;
vector<int> m_min;
};

总结

熟练掌握各种数据结构, 求最小值要分析stack最小值的特点.