Min Stack ใน Python

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

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• เริ่มต้นสแต็กโดยองค์ประกอบขั้นต่ำเป็นอินฟินิตี้
• สำหรับการกดการดำเนินการ push(x)
  • ถ้า x
  • ดัน x ลงในสแต็ก
• สำหรับการดำเนินการป๊อป pop()
  • t :=องค์ประกอบด้านบน
  • ลบ t ออกจาก stack
  • ถ้า t เป็น min แล้ว min :=องค์ประกอบด้านบนของสแต็ก
• สำหรับการทำงานด้านบน top()
  • เพียงแค่ส่งคืนองค์ประกอบด้านบน
• สำหรับการดำเนินการ getMin 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