1.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.

Example 1:

Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output
[null,null,null,null,-3,null,0,-2]

Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top();    // return 0
minStack.getMin(); // return -2

Solution:

class MinStack
{
public:
    /** initialize your data structure here. */

    vector<int> v;

    int t;
    
    MinStack()
    {
        t = -1;
    }

    void push(int x)
    {
        t++;
        v.insert(v.begin() + t, x);
    }

    void pop()
    {
        if (t == -1)
        {
            return;
        }
        t--;
    }

    int top()
    {
        if (t == -1)
        {
            return -9;
        }
        return v[t];
    }

    int getMin()
    {

        stack<int> s;
        for (int i = 0; i <= t; i++)
        {
            if (s.empty())
            {
                s.push(v[i]);
            }
            else
            {
                if (v[i] < s.top())
                {
                    s.push(v[i]);
                }
            }
        }

        return s.top();
    }
};

Time Complexity: O(n)

Solution: (Using two stacks)

class MinStack
{
public:
    /** initialize your data structure here. */
    stack<int> s;
    stack<int> m;

    MinStack()
    {
    }

    void push(int x)
    {
        s.push(x);
        if (m.empty() || x <= m.top())
        {
            m.push(x);
        }
    }

    void pop()
    {

        if (!s.empty())
        {

            if (!m.empty() && s.top() == m.top())
            {
                m.pop();
                s.pop();
            }
            else
            {
                s.pop();
            }
        }
    }

    int top()
    {

        return s.top();
    }

    int getMin()
    {

        return m.top();
    }
};

Time Complexity: O(1)