Min Stack

Bài toán

Thiết kế một Stack hỗ trợ các thao tác push, pop, top, và getMin (lấy phần tử nhỏ nhất). Yêu cầu: Tất cả các hàm phải chạy trong thời gian hằng số $O(1)$.

interface MinStack {
    push(val: number): void;
    pop(): void;
    top(): number;
    getMin(): number;
}

Phân Tích & Tiếp Cận

Vấn đề nếu chỉ dùng 1 biến minVal

Nếu ta chỉ dùng một biến minVal để lưu số nhỏ nhất.

• Khi push(2), minVal = 2. push(1), minVal = 1. Ổn.
• Nhưng khi pop() số 1 ra, làm sao ta biết giá trị nhỏ nhất trước đó (số 2) là bao nhiêu để khôi phục? -> Ta cần "nhớ" lại lịch sử min.

Giải pháp: Hai Stack (hoặc Stack cặp)

Ta dùng thêm một stack phụ (minStack) song song với stack chính.

• mainStack: Lưu giá trị thật.
• minStack: Lưu "giá trị nhỏ nhất tính đến thời điểm hiện tại".

Quy trình:

1. Push val:
   • Push vào mainStack.
   • Lấy min giữa val và đỉnh của minStack. Push giá trị này vào minStack.
2. Pop:
   • Pop cả mainStack và minStack.
3. GetMin:
   • Lấy đỉnh của minStack.

Ví dụ: Push [5, 2, 8, 1]

• Main: [5] -> Min: [5] (Min là 5)
• Main: [5, 2] -> Min: [5, 2] (Min là 2)
• Main: [5, 2, 8] -> Min: [5, 2, 2] (8 > 2 nên Min vẫn là 2)
• Main: [5, 2, 8, 1] -> Min: [5, 2, 2, 1] (Min là 1)

Khi Pop 1 ra -> Min quay về 2. Chính xác!

class MinStack {
    private stack: number[] = [];
    private minStack: number[] = [];

    push(val: number): void {
        this.stack.push(val);
        
        // Push vào minStack giá trị min mới
        // Nếu minStack rỗng, min chính là val
        // Ngược lại, min là Math.min(val, currentMin)
        if (this.minStack.length === 0) {
            this.minStack.push(val);
        } else {
            const currentMin = this.minStack[this.minStack.length - 1];
            this.minStack.push(Math.min(val, currentMin));
        }
    }

    pop(): void {
        this.stack.pop();
        this.minStack.pop();
    }

    top(): number {
        return this.stack[this.stack.length - 1];
    }

    getMin(): number {
        return this.minStack[this.minStack.length - 1];
    }
}

• Time Complexity: $O(1)$ cho mọi thao tác.
• Space Complexity: $O(n)$ - Tốn gấp đôi bộ nhớ để duy trì stack phụ.

Pattern Nhận Diện

Để truy xuất $O(1)$ các thuộc tính tổng hợp (min, max, sum) của một cấu trúc dữ liệu động (như Stack), ta thường cần lưu trữ song song trạng thái đó tại mỗi bước thay đổi. Đánh đổi Space lấy Time.