# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python 3
#     language: python
#     name: python3
# ---

# ### 155. Min Stack

# #### Content
# <p>Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.</p>
#
# <p>Implement the <code>MinStack</code> class:</p>
#
# <ul>
# 	<li><code>MinStack()</code> initializes the stack object.</li>
# 	<li><code>void push(val)</code> pushes the element <code>val</code> onto the stack.</li>
# 	<li><code>void pop()</code> removes the element on the top of the stack.</li>
# 	<li><code>int top()</code> gets the top element of the stack.</li>
# 	<li><code>int getMin()</code> retrieves the minimum element in the stack.</li>
# </ul>
#
# <p>&nbsp;</p>
# <p><strong>Example 1:</strong></p>
#
# <pre>
# <strong>Input</strong>
# [&quot;MinStack&quot;,&quot;push&quot;,&quot;push&quot;,&quot;push&quot;,&quot;getMin&quot;,&quot;pop&quot;,&quot;top&quot;,&quot;getMin&quot;]
# [[],[-2],[0],[-3],[],[],[],[]]
#
# <strong>Output</strong>
# [null,null,null,null,-3,null,0,-2]
#
# <strong>Explanation</strong>
# 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
# </pre>
#
# <p>&nbsp;</p>
# <p><strong>Constraints:</strong></p>
#
# <ul>
# 	<li><code>-2<sup>31</sup> &lt;= val &lt;= 2<sup>31</sup> - 1</code></li>
# 	<li>Methods <code>pop</code>, <code>top</code> and <code>getMin</code> operations will always be called on <strong>non-empty</strong> stacks.</li>
# 	<li>At most <code>3 * 10<sup>4</sup></code> calls will be made to <code>push</code>, <code>pop</code>, <code>top</code>, and <code>getMin</code>.</li>
# </ul>
#

# #### Difficulty: Easy, AC rate: 47.6%
#
# #### Question Tags:
# - Stack
# - Design
#
# #### Links:
#  🎁 [Question Detail](https://leetcode.com/problems/min-stack/description/) | 🎉 [Question Solution](https://leetcode.com/problems/min-stack/solution/) | 💬 [Question Discussion](https://leetcode.com/problems/min-stack/discuss/?orderBy=most_votes)
#
# #### Hints:
# <details><summary>Hint 0  🔍</summary>Consider each node in the stack having a minimum value. (Credits to @aakarshmadhavan)</details>
#

# #### Sample Test Case
# ["MinStack","push","push","push","getMin","pop","top","getMin"]
# [[],[-2],[0],[-3],[],[],[],[]]

# ---
# What's your idea?
#
# 栈中每个节点都可以暂存该节点入栈时的快照信息。此处的信息是入栈时全局最小值
#
# ---

# + isSolutionCode=true
class MinStack:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = [(0, 2**31-1)]

    def push(self, val: int) -> None:
        self.stack.append((val, min(val, self.stack[-1][1])))

    def pop(self) -> None:
        self.stack.pop()

    def top(self) -> int:
        return self.stack[-1][0]

    def getMin(self) -> int:
        return self.stack[-1][1]


# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

# +
ops = ["MinStack","push","push","push","getMin","pop","top","getMin"]
params = [[],[-2],[0],[-3],[],[],[],[]]

stack = MinStack()
results = []
for op, param in zip(ops[1:], params[1:]):
    if op == 'push':
        results.append(stack.push(param[0]))
    elif op == 'getMin':
        results.append(stack.getMin())
    elif op == 'pop':
        results.append(stack.pop())
    elif op == 'top':
        results.append(stack.top())

results
# -

import sys, os; sys.path.append(os.path.abspath('..'))
from submitter import submit
submit(155)

StarcoderdataJupyterScriptsDedupFiltered