leetcode Question: Min Stack

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]