07. Min Stack

📌 07. Min Stack

7.1 Bài toán

Thiết kế một stack hỗ trợ các thao tác sau, tất cả đều O(1):

• push(x) — thêm phần tử x
• pop() — xóa phần tử đỉnh
• top() — xem phần tử đỉnh
• getMin() — trả về phần tử nhỏ nhất trong stack

Khó ở đâu? Thao tác getMin() thông thường cần duyệt toàn bộ stack = O(n). Làm sao giảm xuống O(1)?

Ví dụ thực tế: Bạn quản lý một chồng hồ sơ, bạn muốn biết hồ sơ có số hiệu nhỏ nhất là bao nhiêu bất kỳ lúc nào, mà không cần lật từng hồ sơ.

7.2 Cách 1: Dùng 2 Stack

Ý tưởng: Dùng thêm một stack phụ min_stack để lưu giá trị min tương ứng với mỗi trạng thái của stack chính.

• Khi push(x): push x vào main stack. Nếu x <= min hiện tại (hoặc min_stack rỗng), push x vào min_stack.
• Khi pop(): pop từ main stack. Nếu giá trị pop == top của min_stack, pop luôn min_stack.
• getMin(): trả về top của min_stack.

Flowchart:

getMin()return min_stack.top()pop()CóKhôngval = main_stack.pop()val == min_stack.top()?min_stack.pop()Không pop min_stackpush(x)CóKhôngpush x vào main_stackmin_stack rỗng HOẶC x <= min_stack.top()push x vào min_stackKhông push vào min_stack

7.3 Mô phỏng chi tiết

push(5):  main=[5],      min=[5]        ← 5 là min đầu tiên
push(3):  main=[5,3],    min=[5,3]      ← 3 <= 5 → push vào min
push(7):  main=[5,3,7],  min=[5,3]      ← 7 > 3 → không push vào min
push(3):  main=[5,3,7,3], min=[5,3,3]   ← 3 <= 3 → push vào min
push(1):  main=[5,3,7,3,1], min=[5,3,3,1] ← 1 <= 3 → push vào min

getMin() → 1 ✓

pop():    val=1, 1==min.top(1) → pop min
          main=[5,3,7,3], min=[5,3,3]

getMin() → 3 ✓

pop():    val=3, 3==min.top(3) → pop min
          main=[5,3,7], min=[5,3]

getMin() → 3 ✓

pop():    val=7, 7!=min.top(3) → không pop min
          main=[5,3], min=[5,3]

getMin() → 3 ✓

7.4 Code — Cách 1: Two Stacks

Python

class MinStack:
    """
    Min Stack dùng 2 stack.
    Mọi thao tác O(1) time, O(n) space.
    """
 
    def __init__(self):
        self.main_stack = []
        self.min_stack = []   # Lưu min tại mỗi trạng thái
 
    def push(self, x):
        """O(1)"""
        self.main_stack.append(x)
        # Push vào min_stack nếu x <= min hiện tại
        if not self.min_stack or x <= self.min_stack[-1]:
            self.min_stack.append(x)
 
    def pop(self):
        """O(1)"""
        if not self.main_stack:
            raise IndexError("Stack rỗng!")
        val = self.main_stack.pop()
        # Nếu giá trị pop là min hiện tại → pop luôn min_stack
        if val == self.min_stack[-1]:
            self.min_stack.pop()
        return val
 
    def top(self):
        """O(1)"""
        if not self.main_stack:
            raise IndexError("Stack rỗng!")
        return self.main_stack[-1]
 
    def getMin(self):
        """O(1)"""
        if not self.min_stack:
            raise IndexError("Stack rỗng!")
        return self.min_stack[-1]
 
 
# --- Test ---
ms = MinStack()
ms.push(5)
ms.push(3)
ms.push(7)
ms.push(3)
ms.push(1)
print(ms.getMin())  # 1
ms.pop()             # pop 1
print(ms.getMin())  # 3
ms.pop()             # pop 3
print(ms.getMin())  # 3
ms.pop()             # pop 7
print(ms.getMin())  # 3

Python — MinStack (LeetCode #155 format)

class MinStackLeetCode:
    """
    Format giống LeetCode #155.
    Dùng list làm cả main_stack và min_stack.
    """
 
    def __init__(self):
        self.main_stack = []
        self.min_stack = []
 
    def push(self, val: int) -> None:
        self.main_stack.append(val)
        # Push vào min_stack nếu val <= min hiện tại
        if not self.min_stack or val <= self.min_stack[-1]:
            self.min_stack.append(val)
 
    def pop(self) -> None:
        val = self.main_stack.pop()
        if val == self.min_stack[-1]:
            self.min_stack.pop()
 
    def top(self) -> int:
        return self.main_stack[-1]
 
    def getMin(self) -> int:
        return self.min_stack[-1]
 
 
# --- Test (giống LeetCode) ---
ms = MinStackLeetCode()
ms.push(-2)
ms.push(0)
ms.push(-3)
print(ms.getMin())  # -3
ms.pop()
print(ms.top())     # 0
print(ms.getMin())  # -2

7.5 Cách 2: Dùng 1 Stack — Lưu pair (value, current_min)

Mỗi phần tử trong stack là một cặp (value, min_at_this_point).

class MinStackPair:
    """Min Stack lưu pair (value, min). Dễ hiểu hơn."""
 
    def __init__(self):
        self.stack = []  # Mỗi phần tử là (value, current_min)
 
    def push(self, x):
        current_min = min(x, self.stack[-1][1]) if self.stack else x
        self.stack.append((x, current_min))
 
    def pop(self):
        return self.stack.pop()[0]
 
    def top(self):
        return self.stack[-1][0]
 
    def getMin(self):
        return self.stack[-1][1]
 
 
# --- Test ---
ms = MinStackPair()
ms.push(5)   # stack: [(5,5)]
ms.push(3)   # stack: [(5,5), (3,3)]
ms.push(7)   # stack: [(5,5), (3,3), (7,3)]
ms.push(1)   # stack: [(5,5), (3,3), (7,3), (1,1)]
print(ms.getMin())  # 1
ms.pop()
print(ms.getMin())  # 3

7.6 Cách 3: O(1) Space — Không dùng stack phụ (nâng cao)

Ý tưởng: Lưu min_val riêng. Khi push x < min_val hiện tại, push 2*x - min_val (giá trị mã hóa) và cập nhật min_val = x. Khi pop, nếu giá trị pop < min_val thì biết đây là giá trị mã hóa, khôi phục min_val cũ.

class MinStackO1Space:
    """Min Stack O(1) extra space (ngoài stack chính)."""
 
    def __init__(self):
        self.stack = []
        self.min_val = float('inf')
 
    def push(self, x):
        if not self.stack:
            self.stack.append(x)
            self.min_val = x
        elif x >= self.min_val:
            self.stack.append(x)
        else:
            # Lưu giá trị mã hóa: 2*x - min_val < x < min_val
            self.stack.append(2 * x - self.min_val)
            self.min_val = x
 
    def pop(self):
        if not self.stack:
            raise IndexError("Stack rỗng!")
        top_val = self.stack.pop()
        if top_val < self.min_val:
            # Giá trị thực = min_val hiện tại
            actual = self.min_val
            # Khôi phục min_val cũ
            self.min_val = 2 * self.min_val - top_val
            return actual
        return top_val
 
    def top(self):
        if not self.stack:
            raise IndexError("Stack rỗng!")
        top_val = self.stack[-1]
        if top_val < self.min_val:
            return self.min_val  # Giá trị thực là min_val
        return top_val
 
    def getMin(self):
        return self.min_val

Chứng minh tại sao nó hoạt động:

Khi push x với x < min_val:

• Lưu encoded = 2*x - min_val vào stack
• Vì x < min_val → encoded = 2*x - min_val < 2*min_val - min_val = min_val
• Vậy encoded < x < min_val (cũ)
• Cập nhật min_val = x

Khi pop và thấy top_val < min_val:

• Biết đây là giá trị mã hóa
• Giá trị thực = min_val hiện tại
• min_val cũ = 2 * min_val - top_val = 2*x - (2*x - min_old) = min_old ✓

7.7 So sánh các cách

Cách	Time (mỗi op)	Extra Space	Ưu điểm
Two Stacks	O(1)	O(n)	Đơn giản, dễ hiểu
Pair Stack	O(1)	O(n)	Rất dễ cài đặt
O(1) Space	O(1)	O(1)	Tiết kiệm bộ nhớ nhất

Lưu ý: Cách O(1) space chỉ hoạt động với kiểu số (integer/float). Với kiểu dữ liệu khác, dùng cách two stacks hoặc pair.

7.8 Chứng minh tất cả thao tác O(1)

Mỗi thao tác (push, pop, top, getMin) chỉ gồm:

• Tối đa 1 phép so sánh: O(1)
• Tối đa 1 phép push/pop trên stack: O(1)
• Tối đa 1 phép tính số học: O(1)

Không có vòng lặp hay đệ quy → O(1) worst case.