Notes:
This is an interesting question.
In order to increase time complexity, we usually need to sacrifice some space.
Here I want to share two ways to solve this problem.
1): use two stacks. One is a normal stack. The second one is used to record the instant minimum only as pushing elements into the first stack.
2): use one stack only. Every time after we push in a new element, we will push in the instant minimum first.
Let realize the first one first.
See the code below:
class MinStack {
public:
/** initialize your data structure here. */
MinStack() {
}
void push(int x) {
sk1.push(x);
if(sk2.empty() || sk2.top() >= x) sk2.push(x);
}
void pop() {
int x = sk1.top();
sk1.pop();
if(x==sk2.top()) sk2.pop();
}
int top() {
return sk1.top();
}
int getMin() {
return sk2.top();
}
private:
stack<int> sk1, sk2;
};
/**
* Your MinStack object will be instantiated and called as such:
* MinStack* obj = new MinStack();
* obj->push(x);
* obj->pop();
* int param_3 = obj->top();
* int param_4 = obj->getMin();
*/
Now let see the second one:
class MinStack {
public:
/** initialize your data structure here. */
MinStack() {
}
void push(int x) {
int y = sk.empty() ? x : min(x, sk.top());
sk.push(x);
sk.push(y);
}
void pop() {
sk.pop();
sk.pop();
}
int top() {
int x = sk.top();
sk.pop();
int res = sk.top();
sk.push(x);
return res;
}
int getMin() {
return sk.top();
}
private:
stack<int> sk;
};
/**
* Your MinStack object will be instantiated and called as such:
* MinStack* obj = new MinStack();
* obj->push(x);
* obj->pop();
* int param_3 = obj->top();
* int param_4 = obj->getMin();
*/
