Min Stack:

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:

There are several ways to solve this problem.
(1) Use an extra stack to store the minimum value. The space is O(n), time O(1)
(2) Use a variable to store the minimum value. The time is O(n), space O(1)

Note that, in the python code, a little modification is needed to pass the OJ test.
Just using two stacks is not satisfied with the memory requirement.
So, the min stack stores [min_val, count] instead of each min_val.
e.g.,
Push into Stack:
st     min_st
2      [2,1]

st     min_st
0      [0,1]
2      [2,1]

st     min_st
3
0      [0,1]
2      [2,1]

st     min_st
0
3
0      [0,2]
2      [2,1]

Pop:
st     min_st
3
0      [0,1]
2      [2,1]

st     min_st
0      [0,1]
2      [2,1]

st     min_st
2      [2,1]

Code(C++):

class MinStack {
deque<int> st;
int minVal;
public:
void push(int x) {
if (st.empty() || x<minVal){
minVal = x;
}
st.push_front(x);
}

void pop() {
if (st.front() == minVal){
st.pop_front();
minVal=INT_MAX;
for (deque<int>::iterator it = st.begin();it!=st.end();it++){
minVal = min(minVal,*it);
}
}else{
st.pop_front();
}

}

int top() {
return st.front();
}

int getMin() {
return minVal;
}
};


Code(Python):

class MinStack:
# @param x, an integer
# @return an integer
def __init__(self):
self.l_num = []
self.minval = []

def push(self, x):
if len(self.l_num) == 0 or len(self.minval) == 0:
self.minval.append([x,1])
else:
if x < self.getMin():
self.minval.append([x,1])
elif x == self.getMin():
self.minval[-1][1] += 1
self.l_num.append(x)

# @return nothing
def pop(self):
if self.l_num[-1] == self.minval[-1][0]:
self.l_num.pop(-1)
if (self.minval[-1][1]>1):
self.minval[-1][1] -= 1
else:
self.minval.pop(-1)
else:
self.l_num.pop(-1)

# @return an integer
def top(self):
return self.l_num[-1]

# @return an integer
def getMin(self):
return self.minval[-1][0]