155. Min Stack

Easy

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.

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³¹ <= val <= 2³¹ - 1
Methods pop, top and getMin operations will always be called on non-empty stacks.
At most 3 * 10⁴ calls will be made to push, pop, top, and getMin.

 # class ListNode:
#     def __init__(self, x, min = None):
#         self.val = x
#         self.next = None
#         self.min = min

class MinStack:

#     def __init__(self):
#         self.head = None
#         self.min = None


#     def push(self, value: int) -> None:
#         if not self.head:
#             self.head = ListNode(value, value)
#             self.min = value
#         else:
#             min = value if value < self.min else self.min
#             self.min = min
#             node = ListNode(value,  min)
#             node.next = self.head
#             #self.head.next = node
#             self.head = node

#     def pop(self) -> None:
#         if self.head is not None:
#             self.head = self.head.next
#             if self.head is not None:
#                 self.min = self.head.min
#             else:
#                 self.min = None

#     def top(self) -> int:
#         if self.head is not None:
#             return self.head.val


#     def getMin(self) -> int:
#         return self.min
    def __init__(self):
        self.stack = []

    def push(self, value):
        if not self.stack: # empty stack
            self.stack.append([value, value])
        else:
            minimum = value if value < self.getMin() else self.getMin()
            self.stack.append( [value, minimum] )

    def getMin(self):
        #print(self.stack)
        return self.stack[-1][1]

    def pop(self):
        self.stack.pop()

    def top(self):
        if self.stack is not None:
            return self.stack[-1][0]


# 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()

155. Min Stack

Random Note