Min Stack ใน Python

ที่นี่เราจะดูวิธีสร้างสแต็กที่สามารถทำ push, pop, top และดึงค่าต่ำสุดได้ในเวลาคงที่ ฟังก์ชันจะเป็น push(x), pop(), top() และ getMin()

วิธีการแก้ปัญหา

• เริ่มต้นสแต็กด้วยค่าต่ำสุดเป็น infinity
• สำหรับการ push(x):
  • ถ้า x < min ให้อัปเดต min := x
  • push x เข้าสแต็ก
• สำหรับการ pop():
  • t := องค์ประกอบบนสุด
  • ลบ t ออกจากสแต็ก
  • ถ้า t เป็น min ให้ min := องค์ประกอบบนสุดของสแต็ก
• สำหรับการ top():
  • คืนค่าองค์ประกอบบนสุดโดยตรง
• สำหรับการ getMin():
  • คืนค่าองค์ประกอบต่ำสุด

ตัวอย่างโค้ด

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