• 27.1%

https://leetcode.com/problems/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.

min表示当前的最小值，如果新的x不改变最小值，push进去。如果改变或者等于最小值，先把min压入，再把min更改为x，把x压入。

[-2], -2

[-2, 0], -2

[-2, 0, -2, -3] -3

[-2, 0, -2, -3] -3

[-2, 0] -2

[-2] -2

pop时，检查与min的关系。

Dec 7th, 2017

56ms, September 13, 2016

https://discuss.leetcode.com/topic/18556/c-using-two-stacks-quite-short-and-easy-to-understand

C++ using two stacks, quite short and easy to understand

https://discuss.leetcode.com/topic/28435/c-o-1-solution

C++ O(1) solution

https://discuss.leetcode.com/topic/11985/my-python-solution

My Python solution

https://discuss.leetcode.com/topic/4953/share-my-java-solution-with-only-one-stack

Share my Java solution with ONLY ONE stack

The question is ask to construct One stack. So I am using one stack.

The idea is to store the gap between the min value and the current value;

The problem for my solution is the cast. I have no idea to avoid the cast. Since the possible gap between the current value and the min value could be Integer.MAX_VALUE-Integer.MIN_VALUE;

https://discuss.leetcode.com/topic/7020/java-accepted-solution-using-one-stack

Java accepted solution using one stack