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.
Analysis:
Apparently, we need to use extra space to store the minimum element of the stack. We can use one stack s to store the pushed element and another stack sMin to store minimum elements appearing so far. Whenever an element x is pushed, if it is less than current minimum (at the top of sMin stack), push x to the sMin; otherwise, the top of the sMin is the minimum and we push it to sMin;
class MinStack {
stack<int> s;
stack<int> sMin;
public:
void push(int x) {
s.push(x);
if (sMin.empty() || x < sMin.top())
sMin.push(x);
else
sMin.push(sMin.top());
}
void pop() {
s.pop();
sMin.pop();
}
int top() {
return s.top();
}
int getMin() {
return sMin.top();
}
};
However, it could not pass Leetcode oj as Memory Limit Exceeded. By looking at the solution again, we notice that if x is greater than minimum value, there is no need to push the sMin top value. Just do some special handle when popping the element: if the element is greater than minimum, do not pop sMin.
class MinStack {
stack<int> s;
stack<int> sMin;
public:
void push(int x) {
s.push(x);
if (sMin.empty() || x <= sMin.top())
sMin.push(x);
}
void pop() {
if (s.top() <= sMin.top())
sMin.pop();
s.pop();
}
int top() {
return s.top();
}
int getMin() {
return sMin.top();
}
};
In addition, we notice that if all the pushed elements are the same, there are still spaces wasted. It is possible to have a better solution so that few spaces needed for sMin.
No comments:
Post a Comment