Min_stack

发表于 Waline： 阅读次数： 本文字数： 577 阅读时长 ≈ 1 分钟

还是比较简单的，但是这个跟我在宁夏坑队友的一个题一模一样，权当纪念吧

题目：实现一个数据结构，这个数据结构需要实现栈的插入，栈的弹出，返回栈顶元素，返回栈内最小值四种操作。

My Ans：用vector保存从栈底到栈顶的前缀Min，可以知道每次插入的时候需要在Vector中插入Min(input,Vector.back())；

跑的不是很快…28ms beat 50.39%而已

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class MinStack {
public:
    /** initialize your data structure here. */
    vector<int>m;
    stack<int>st;
    MinStack() {
        m.clear();
    }
    void push(int x) {
        st.push(x);
        if(m.empty()) m.push_back(x);
        else m.push_back(min(m.back(),x));
    }
    void pop() {
        m.pop_back();
        st.pop();
    }
    int top() {
        return st.top();
    }
    int getMin() {
        return m.back();
    }
};