Min_stack

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

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

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();
}
};