পাইথনে মিন স্ট্যাক ইমপ্লিমেন্টেশন

একটি স্ট্যাক ডিজাইন করতে হবে যা push, pop, top এবং getMin অপারেশনগুলো O(1) সময়ে করতে পারবে।

সমাধানের পদ্ধতি

1. স্ট্যাক এবং min ভেরিয়েবল (ইনিশিয়ালি ইনফিনিটি) রাখুন।
2. Push(x): যদি x <= min হয়, তবে পুরনো min স্টকে পুশ করুন, তারপর min = x এবং x পুশ করুন।
3. Pop(): টপ এলিমেন্ট পপ করুন। যদি সেটি min হয়, তবে আবার পপ করে নতুন min সেট করুন।
4. Top(): টপ এলিমেন্ট রিটার্ন করুন।
5. GetMin(): min রিটার্ন করুন।

উদাহরণ কোড

class MinStack(object):
    min = float('inf')
    def __init__(self):
        self.min = float('inf')
        self.stack = []
    def push(self, x):
        if x <= self.min:
            self.stack.append(self.min)
            self.min = x
        self.stack.append(x)
    def pop(self):
        t = self.stack[-1]
        self.stack.pop()
        if self.min == t:
            self.min = self.stack[-1]
            self.stack.pop()
    def top(self):
        return self.stack[-1]
    def getMin(self):
        return self.min

m = MinStack()
m.push(-2)
m.push(0)
m.push(-3)
print(m.getMin())
m.pop()
print(m.top())
print(m.getMin())

ইনপুট

m = MinStack() m.push(-2) m.push(0) m.push(-3) print(m.getMin()) m.pop() print(m.top()) print(m.getMin())

আউটপুট

-3 0 -2