155. Min Stack

Solution 1: Use Two Stack

class MinStack:

    def __init__(self):
        self.minStack = []
        self.normalStack = []

    def push(self, val: int) -> None:
        self.normalStack.append(val)
        if not self.minStack or val <= self.getMin():
            self.minStack.append(val)

    def pop(self) -> None:
        if self.normalStack:
            if self.top() == self.getMin():
                self.minStack.pop()
            self.normalStack.pop()

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

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

Time Complexity: O(N)
Space Complexity: O(N)

Solution 2: Linked-list with minValue Node

Time Complexity: O(N)
Space Complexity: O(N)

Reference

https://leetcode.com/problems/min-stack/solutions/49016/c-using-two-stacks-quite-short-and-easy-to-understand/?orderBy=most_votes
https://leetcode.com/problems/min-stack/solutions/49010/clean-6ms-java-solution/

Follow-up: 232. Implement Queue using Stacks

Follow-up: 716. Max Stack