Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
- push(x) -- Push element x onto stack.
- pop() -- Removes the element on top of the stack.
- top() -- Get the top element.
- getMin() -- Retrieve the minimum element in the stack.
这道题神烦，总是超过内存限制，思路就是那个但是就是内存超了，不明觉历，拿到要用c数组？
总之需要注意两点：
1.每个操作都要O(1)
2.pop了以后注意min的变化
class MinStack {
private:
vector<int> min;
vector<int> data;
public:
void push(int x) {
data.push_back(x);
if (min.size() == || data[min.at(min.size()-)] > x) {
min.push_back((int)data.size()-);
}
}
void pop() {
if (data.size()) {
if (min.size() > && min.at(min.size()-) == data.size()-) {
min.pop_back();
}
data.pop_back();
}
}
int top() {
if (data.size() > )
return data.at(data.size()-);
return INT_MIN;
}
int getMin() {
return data.at(min.at(min.size()-));
}
};