Mô phỏng thuật toán Ngăn xếp có Min O(1)

Min Stack · Nhóm: Ngăn xếp & Hàng đợi

Ngăn xếp hỗ trợ lấy phần tử nhỏ nhất trong O(1) nhờ một ngăn xếp phụ chạy song song.

Ý tưởng

Mỗi lần push, đẩy giá trị lên stack chính và đẩy min tính tới thời điểm đó lên stack-min.

getMin chỉ đọc đỉnh stack-min vì đó luôn là min hiện thời.

pop rút song song đỉnh cả hai stack, min tự lùi về giá trị trước đó.

Vì sao đúng

Đỉnh stack-min luôn lưu min tích lũy từ đáy tới đỉnh nên không thao tác nào phải quét lại toàn bộ ngăn xếp.

Mã Python

class MinStack:
    def __init__(self):
        self.st = []            # main stack
        self.mn = []            # parallel min-stack
    def push(self, x):
        self.st.append(x)
        m = x if not self.mn else min(x, self.mn[-1])
        self.mn.append(m)       # min of everything below + itself
    def pop(self):
        self.mn.pop()
        return self.st.pop()
    def getMin(self):
        return self.mn[-1]      # O(1): top of min-stack

Mở trang để xem mô phỏng từng bước và xuất slide bài giảng.