Designing Data Structures for Efficient Operations — தரவு அமைப்பு வடிவமைப்பு

வடிவமைப்பு — அடிப்படை + invariant; min-stack — (value, min_so_far).

உண்மை உலகில் இது ஏன் முக்கியம்?

LRU — map+பட்டியல். Undo — இரட்டை stack.

மையக் கருத்து (மாணவர்களுக்கான விளக்கம்)

செயல்பாடு பட்டியல்; செலவு நிரூபணம்; மாதிரி.

Pythonில் முயற்சி செய்வோம்

class MinStack:
    def __init__(self) -> None:
        self.st: list[tuple[int, int]] = []

    def push(self, x: int) -> None:
        m = x if not self.st else min(x, self.st[-1][1])
        self.st.append((x, m))

    def pop(self) -> None:
        self.st.pop()

    def get_min(self) -> int:
        return self.st[-1][1]


ms = MinStack()
ms.push(3)
ms.push(1)
ms.push(2)
print(ms.get_min())

அடிக்கடி நேரும் தவறுகள்

• API முன் மேம்பாடு.
• list pop(0) — O(n).

முக்கியச் சுருக்கக் குறிப்புகள்

• முதல் சரி; பின் profile.
• invariant assert.