class MinStack {
public:
vector<int> a;
vector<int> min;
MinStack() {
min.push_back(2147483647);
}
void push(int x) {
a.push_back(x);
if (x < min.back()) {
min.push_back(x);
} else {
min.push_back(min.back());
}
}
void pop() {
a.pop_back();
min.pop_back();
}
int top() {
return a.back();
}
int getMin() {
return min.back();
}
};
C++ O(1) solution


said in C++ O(1) solution:
2147483647
I think you could use INT_MAX instead of 2147483647。

In fact you could use only one vector
class MinStack { vector<int> a; int min; public: /** initialize your data structure here. */ MinStack() { min = INT_MAX; } void push(int x) { if(x <= min) { a.push_back(min); min = x; } a.push_back(x); } void pop() { int t = a.back(); a.pop_back(); if (t == min) { min = a.back(); a.pop_back(); } } int top() { return a.back(); } int getMin() { return min; } };