:orphan:

Min Stack
=========

.. highlight:: none

Problem
-------
https://leetcode.com/problems/min-stack/

Design a stack that supports push, pop, top, and retrieving the minimum
element in constant time.

Implement the ``MinStack`` class:

- ``MinStack()`` initializes the stack object.
- ``void push(int val)`` pushes the element ``val`` onto the stack.
- ``void pop()`` removes the element on the top of the stack.
- ``int top()`` gets the top element of the stack.
- ``int getMin()`` retrieves the minimum element in the stack.

You must implement a solution with ``O(1)`` time complexity for each
function.

 

**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

 

**Constraints:**

- ``-2``\ :sup:```31```\ ``<= val <= 2``\ :sup:```31```\ ``- 1``
- Methods ``pop``, ``top`` and ``getMin`` operations will always be
  called on **non-empty** stacks.
- At most ``3 * 10``\ :sup:```4``` calls will be made to ``push``,
  ``pop``, ``top``, and ``getMin``.

.. highlight:: python

Pattern
-------
Stack, Design

Approaches
----------

.. tab-set::

    .. tab-item:: Two Stacks

        **Code**

        .. literalinclude:: ../problems/medium/min-stack/min_stack__two_stacks.py
            :language: python
            :lines: 14-

        **Test**

        >>> from min_stack__two_stacks import MinStack
        >>> s = MinStack()
        >>> s.push(-2); s.push(0); s.push(-3)
        >>> s.getMin()
        -3
        >>> s.pop()
        >>> s.top()
        0
        >>> s.getMin()
        -2

        .. autoclass:: min_stack__two_stacks.MinStack
           :members:
           :show-inheritance:
           :undoc-members: