My simple C++ solution with ONLY ONE STACK AND NO OTHER MEMBER VARIABLE!!! [Avg. 40.8 ms in 5 runs]


  • 0
    S

    My idea is to push the element and also the current min. into the stack and do corresponding operations needed.
    The stack looks like (from top to bottom):
    min2 => x2 => min1 => x1,
    where min2 = min(x1,x2), min1 = x1. xn is the n'th pushed number.

    The following is my code.

    class MinStack {
    public:
        /** initialize your data structure here. */
        MinStack() {
            m_stack = stack<int>();
        }
        
        void push(int x) {
            
            if(m_stack.empty() || x < m_stack.top()){
                m_stack.push(x);
                m_stack.push(x); // in the case ==> min == x 
            }else{
                int currentMin = m_stack.top();
                m_stack.push(x);
                m_stack.push(currentMin);
            }
            
        }
        
        void pop() {
            
            // remember to pop twice, m_stack.top() remains the min. element
            m_stack.pop();
            m_stack.pop();
            
        }
        
        int top() {
            int min = m_stack.top();
            m_stack.pop();
            int realTop = m_stack.top();
            m_stack.push(min);
            
            return realTop;
        }
        
        int getMin() {
            return m_stack.top();
        }
        
    private:
        stack<int> m_stack;
    };
    
    
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.