Ngăn xếp tối thiểu (Min Stack) trong Python

Thiết kế ngăn xếp hỗ trợ push, pop, top, getMin trong thời gian O(1).

Giải pháp

Lưu giá trị nhỏ nhất hiện tại cùng với mỗi phần tử:

• Khởi tạo min = infinity, stack = [].
• push(x): nếu x <= min: push min cũ, cập nhật min = x. Push x.
• pop(): lấy top t. Nếu t == min: pop thêm một lần để lấy min cũ.
• top(): trả về stack[-1].
• getMin(): trả về min.

Ví dụ

Triển khai Python:

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())

Đầu vào

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

Đầu ra

-3 0 -2