155. Min Stack

Problem Statement

link: https://leetcode.com/problems/min-stack/ https://leetcode.cn/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:

Input: ["MinStack","push","push","push","getMin","pop","top","getMin"][[],[-2],[0],[-3],[],[],[],[]] Output: [null,null,null,null,-3,null,0,-2]

Solution Approach

The solution leverages two stacks: one for the main operations and the other to keep track of the minimum elements.

Algorithm

1. Initialization: Create two stacks: the main stack to store all the elements (stack) and another (minstack) to store the minimum values. Initialize minstack with positive infinity.
2. Push operation: Push the value onto the main stack. If the value is less than or equal to the top of the minstack, push it onto the minstack as well.
3. Pop operation: Pop the top value from the main stack. If the popped value is equal to the top of the minstack, pop it from the minstack too.

Implement

    class MinStack:
    def __init__(self):
        self.stack = []
        self.minstack = [float(inf)]

    def push(self, val: int) -> None:
        self.stack.append(val)
        if val <= self.minstack[-1]:
            self.minstack.append(val)

    def pop(self) -> None:
        if self.stack[-1] == self.minstack[-1]:
            self.minstack.pop()
        self.stack.pop()

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

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

    
    

Twitter  facebook  Email