Phỏng vấn

Thiết kế Min Stack O(1) và cài đặt Hàng đợi bằng hai Ngăn xếp (Amortized O(1))

Ngăn xếp (Stack) và hàng đợi (Queue) là hai cấu trúc dữ liệu tuyến tính cơ bản nhất, nhưng các câu hỏi phỏng vấn xoay quanh chúng hiếm khi dừng lại ở việc gọi hàm thư viện. Người phỏng vấn thường đặt ra hai bài toán thiết kế kinh điển: làm sao mở rộng ngăn xếp để truy vấn phần tử nhỏ nhất trong thời gian hằng số $O(1)$ ngay cả khi các phần tử liên tục bị đẩy vào và lấy ra (Min Stack), và làm sao dùng hai ngăn xếp hoạt động theo nguyên tắc vào sau - ra trước (LIFO) để mô phỏng chính xác một hàng đợi vào trước - ra trước (FIFO) với chi phí trung bình khấu hao $O(1)$ trên mỗi thao tác. Bài viết này mổ xẻ bất biến trạng thái và cách chứng minh độ phức tạp của cả hai thiết kế.

Ý chính
  • Bất biến của Min Stack \(O(1)\): Giá trị nhỏ nhất của toàn bộ ngăn xếp tại thời điểm có \(k\) phần tử chỉ phụ thuộc vào \(k\) phần tử đang nằm bên dưới. Bằng cách gắn kèm giá trị nhỏ nhất tích lũy (val, cur_min) vào mỗi nút của ngăn xếp, khi đỉnh ngăn xếp bị pop(), giá trị nhỏ nhất của \(k - 1\) phần tử còn lại lập tức lộ ra ở đỉnh mới mà không cần quét lại.
  • Đảo chiều LIFO thành FIFO bằng hai ngăn xếp: Một lần đổ dữ liệu từ ngăn xếp này sang ngăn xếp kia sẽ đảo ngược thứ tự các phần tử. Do đó, đẩy phần tử vào ngăn xếp đầu vào (in_st) rồi đổ sang ngăn xếp đầu ra (out_st) sẽ đưa phần tử vào sớm nhất lên đúng đỉnh của out_st.
  • Nguyên tắc đổ lười (Lazy Transfer): Chỉ chuyển phần tử từ in_st sang out_st khi và chỉ khi out_st hoàn toàn rỗng. Nếu đổ ngay mỗi lần push hoặc đổ khi out_st còn phần tử, thứ tự FIFO sẽ bị phá vỡ hoặc độ phức tạp bị đẩy lên \(O(n)\) cho mỗi thao tác.
  • Độ phức tạp khấu hao (Amortized \(O(1)\)): Mỗi phần tử trong suốt vòng đời của nó chỉ được đẩy vào in_st đúng \(1\) lần, lấy khỏi in_st đúng \(1\) lần, đẩy vào out_st đúng \(1\) lần và lấy khỏi out_st đúng \(1\) lần. Tổng số phép toán trên \(n\) phần tử là \(4n\), suy ra chi phí trung bình mỗi thao tác là \(O(1)\).

Phần 1: Thiết kế Min Stack truy vấn giá trị nhỏ nhất trong O(1)

Tại sao một biến min_val đơn lẻ không đủ?

Khi mới nghe yêu cầu thiết kế cấu trúc ngăn xếp hỗ trợ bốn thao tác push(x), pop(), top() và getMin() đều trong thời gian \(O(1)\), phản xạ đầu tiên của nhiều người là dùng một ngăn xếp thông thường kèm theo một biến số nguyên min_val cập nhật mỗi khi có phần tử mới nhỏ hơn được đẩy vào.

Cách này hoạt động đúng khi chỉ có thao tác push(x), nhưng sụp đổ ngay khi gọi pop(): giả sử ta lần lượt đẩy 5, 2, 1 vào ngăn xếp. Lúc này min_val = 1. Khi gọi pop() để lấy 1 ra khỏi đỉnh, giá trị nhỏ nhất mới của ngăn xếp phải quay về 2. Nhưng nếu chỉ có một biến min_val, ta không biết giá trị nhỏ nhất trước khi 1 xuất hiện là bao nhiêu nếu không duyệt lại toàn bộ ngăn xếp mất \(O(n)\) thời gian.

Lưu trạng thái nhỏ nhất theo từng tầng ngăn xếp

Điểm đặc biệt của ngăn xếp là các phần tử chỉ được thêm vào và lấy ra ở cùng một đầu (đỉnh ngăn xếp). Điều này kéo theo một tính chất quan trọng: chừng nào phần tử ở tầng thứ \(i\) vẫn còn nằm trong ngăn xếp, thì tập hợp các phần tử từ đáy ngăn xếp (tầng \(1\)) đến tầng \(i\) là hoàn toàn bất biến — không có phần tử nào ở bên dưới nó có thể bị xóa trước nó.

Vì vậy, giá trị nhỏ nhất của tập hợp các phần tử từ đáy đến tầng \(i\), ký hiệu là \(m_i\), là một hằng số cố định ngay từ lúc phần tử thứ \(i\) được đẩy vào:

\[m_i = \begin{cases} x_1 & \text{nếu } i = 1 \\ \min(m_{i-1}, x_i) & \text{nếu } i \gt 1 \end{cases}\]

Từ công thức truy hồi này, ta có hai cách cài đặt chuẩn trong phỏng vấn:

  1. Cách 1 — Ngăn xếp lưu cặp (val, cur_min): Mỗi phần tử trên ngăn xếp là một bộ đôi gồm giá trị thực val và giá trị nhỏ nhất tính từ đáy tới chính nó cur_min. Khi pop(), cặp ở đỉnh bị gỡ bỏ và đỉnh mới bên dưới đã lưu sẵn giá trị nhỏ nhất của phần còn lại.
  2. Cách 2 — Ngăn xếp phụ min_st tiết kiệm bộ nhớ: Tách riêng ngăn xếp chính st (lưu val) và ngăn xếp phụ min_st. Ta chỉ đẩy x vào min_st khi min_st đang rỗng hoặc khi \(x \le \text{min\_st.top()}\) (chú ý dấu \(\le\) bắt buộc phải có dấu bằng để xử lý trường hợp có nhiều phần tử trùng giá trị nhỏ nhất). Khi st.pop() lấy ra giá trị bằng đúng min_st.top(), ta đồng thời gọi min_st.pop().
Min Stack O(1) và Hàng đợi FIFO bằng 2 Ngăn xếp (Amortized O(1)) Trái: lưu cặp (val, min_hiện_tại) — Phải: đổ từ in_st sang out_st khi out_st rỗng Min Stack: push(5), push(2), push(4), push(1) Đỉnh: (1, min=1) -> getMin() = 1 Giữa: (4, min=2) -> sau pop(1) Giữa: (2, min=2) Đáy: (5, min=5) Hàng đợi bằng 2 Stack: push(10, 20, 30) -> pop() in_st (Vào) Đỉnh: 30 Giữa: 20 Đáy: 10 Đổ -> out_st (Ra) Đỉnh: 10 (ra) Giữa: 20 Đáy: 30 Mỗi phần tử chỉ vào in_st 1 lần và sang out_st 1 lần: Chi phí khấu hao = O(1) / thao tác
Min Stack & Queue bằng 2 Stack Min O(1) tại đỉnh và đổ ngược đảo chiều LIFO -> FIFO 1. Min Stack: lưu cặp (val, cur_min) Đỉnh: (1, min=1) -> getMin() = 1 Giữa: (4, min=2), (2, min=2) Đáy: (5, min=5) 2. Queue bằng 2 Stack: push(10, 20, 30) in_st: [10, 20, 30] Đỉnh là 30 (LIFO) out_st: [30, 20, 10] Đỉnh là 10 (ra trước) Chỉ đổ sang out_st khi rỗng -> O(1) khấu hao
Hình 1: So sánh cơ chế hoạt động của Min Stack (bên trái, lưu cặp (val, cur_min) giúp khôi phục ngay giá trị nhỏ nhất sau mỗi lệnh pop) và Hàng đợi bằng 2 ngăn xếp (bên phải, đảo thứ tự LIFO thành FIFO nhờ bước đổ từ in_st sang out_st khi out_st rỗng).

Phần 2: Cài đặt Hàng đợi (FIFO) bằng hai Ngăn xếp (LIFO)

Cơ chế đảo ngược kép bằng hai ngăn xếp in_st và out_st

Hàng đợi (Queue) yêu cầu phần tử nào vào trước phải được lấy ra trước (push vào cuối hàng, pop và peek ở đầu hàng). Trong khi đó, ngăn xếp chỉ cho phép chạm tới phần tử mới nhất ở đỉnh.

Để biến đổi LIFO thành FIFO, ta sử dụng hai ngăn xếp độc lập:

  • Ngăn xếp đầu vào in_st: Chuyên nhận các phần tử mới từ thao tác push(x). Mỗi lệnh push(x) chỉ đơn giản gọi in_st.push(x) trong thời gian \(O(1)\) chặt chẽ. Ở trong in_st, phần tử mới nhất nằm ở đỉnh, còn phần tử cũ nhất bị chôn ở đáy.
  • Ngăn xếp đầu ra out_st: Chuyên phục vụ hai thao tác lấy/xem phần tử đầu hàng là pop() và peek(). Khi cần lấy phần tử ở đầu hàng đợi:
    • Nếu out_st đang còn phần tử, đỉnh của out_st chính là phần tử vào sớm nhất hiện tại — ta đọc hoặc lấy ngay từ out_st.top() trong \(O(1)\).
    • Nếu out_st đang rỗng, ta rút lần lượt toàn bộ phần tử từ đỉnh của in_st và đẩy sang out_st cho tới khi in_st cạn sạch. Nhờ việc lấy từ đỉnh in_st rồi đẩy xuống out_st, thứ tự các phần tử bị lật ngược hoàn toàn: phần tử từng nằm ở đáy in_st (vào sớm nhất) nay vươn lên nằm ở đỉnh out_st!

Chứng minh độ phức tạp khấu hao (Amortized \(O(1)\))

Nhiều ứng viên lo ngại rằng vòng lặp while (!in_st.empty()) trong hàm chuyển dữ liệu có thể chạy \(n\) bước, vậy tại sao bài toán vẫn được công nhận là \(O(1)\)? Câu trả lời nằm ở phân tích khấu hao (Amortized Analysis) theo phương pháp kế toán (Accounting Method):

Xét một chuỗi bất kỳ gồm \(m\) thao tác (push, pop, peek, empty) bắt đầu từ hàng đợi rỗng. Hãy theo dõi hành trình của một phần tử \(x\) cụ thể kể từ lúc nó được đưa vào hàng đợi cho tới lúc nó rời khỏi hàng đợi vĩnh viễn:

  1. Lệnh in_st.push(x): thực hiện đúng \(1\) lần khi gọi push(x).
  2. Lệnh in_st.pop(): thực hiện tối đa \(1\) lần khi out_st rỗng và cần đổ dữ liệu.
  3. Lệnh out_st.push(x): thực hiện tối đa \(1\) lần ngay trong lần đổ dữ liệu đó.
  4. Lệnh out_st.pop(): thực hiện tối đa \(1\) lần khi \(x\) rời khỏi hàng đợi.

Như vậy, mỗi phần tử chỉ chịu tối đa \(4\) phép toán ngăn xếp cơ sở trong suốt cuộc đời của nó, bất kể có bao nhiêu lệnh peek hay pop xen kẽ. Tổng chi phí cho \(m\) thao tác không bao giờ vượt quá \(4m\) phép toán cơ sở, suy ra chi phí trung bình trên mỗi thao tác là \(O(1)\) khấu hao, dù một thao tác pop()/ peek() riêng lẻ tại thời điểm đổ hàng có chi phí trường hợp xấu nhất là \(O(n)\).

Thao tác Min Stack (Lưu cặp (val, cur_min)) Hàng đợi bằng 2 Stack (Trường hợp xấu nhất) Hàng đợi bằng 2 Stack (Trung bình khấu hao)
Thêm phần tử (push) \(O(1)\) chặt chẽ \(O(1)\) chặt chẽ (in_st.push) \(O(1)\)
Lấy phần tử (pop) \(O(1)\) chặt chẽ \(O(n)\) (chỉ khi out_st rỗng phải đổ từ in_st) \(O(1)\) khấu hao
Xem phần tử (top / peek) \(O(1)\) chặt chẽ \(O(n)\) (chỉ khi out_st rỗng phải đổ từ in_st) \(O(1)\) khấu hao
Truy vấn phụ (getMin / empty) \(O(1)\) chặt chẽ \(O(1)\) chặt chẽ \(O(1)\)

Ví dụ chạy tay từng bước cho cả hai cấu trúc

Bảng chạy tay 1: Min Stack với chuỗi thao tác push(5), push(2), push(4), push(1), getMin(), pop(), getMin()

Bước Lệnh gọi Trạng thái ngăn xếp (từ đáy lên đỉnh: (val, cur_min)) Kết quả trả về Giải thích
1 push(5) [(5, 5)] — Ngăn xếp rỗng nên cur_min = 5.
2 push(2) [(5, 5), (2, 2)] — \(\min(5, 2) = 2\), lưu cặp (2, 2) ở đỉnh.
3 push(4) [(5, 5), (2, 2), (4, 2)] — \(\min(2, 4) = 2\), đỉnh mới mang val = 4 nhưng giữ cur_min = 2.
4 push(1) [(5, 5), (2, 2), (4, 2), (1, 1)] — \(\min(2, 1) = 1\), cập nhật cur_min = 1 tại đỉnh.
5 getMin() [(5, 5), (2, 2), (4, 2), (1, 1)] 1 Đọc trực tiếp trường cur_min của cặp ở đỉnh (1, 1).
6 pop() [(5, 5), (2, 2), (4, 2)] — Gỡ cặp (1, 1) khỏi đỉnh; cặp (4, 2) trở thành đỉnh mới.
7 getMin() [(5, 5), (2, 2), (4, 2)] 2 Đọc trường cur_min của đỉnh (4, 2) thu được ngay 2 trong \(O(1)\).

Bảng chạy tay 2: Hàng đợi bằng 2 Stack với chuỗi push(10), push(20), peek(), push(30), pop(), peek()

Bước Lệnh gọi in_st (đáy \(\to\) đỉnh) out_st (đáy \(\to\) đỉnh) Kết quả Giải thích
1 push(10) [10] [] — Đẩy thẳng 10 vào in_st.
2 push(20) [10, 20] [] — Đẩy thẳng 20 vào in_st.
3 peek() [] [20, 10] 10 Do out_st đang rỗng, đổ lần lượt 20 rồi 10 từ in_st sang out_st. Đỉnh out_st là 10.
4 push(30) [30] [20, 10] — Đẩy 30 vào in_st; out_st giữ nguyên không đụng tới.
5 pop() [30] [20] 10 Vì out_st không rỗng, lấy ngay đỉnh 10 của out_st mà không đổ 30 sang.
6 peek() [30] [20] 20 Đỉnh hiện tại của out_st là 20 (phần tử vào thứ hai sau 10).

Cài đặt hoàn chỉnh bằng C++17, Python và Java 21

Đoạn mã dưới đây cài đặt cả hai lớp MinStack và MyQueue trong cùng một chương trình. Chương trình nhận danh sách các lệnh kiểm thử cho MinStack hoặc MyQueue từ luồng nhập chuẩn và in ra dãy kết quả tương ứng.

#include <algorithm>
#include <iostream>
#include <stack>
#include <string>
#include <vector>
using namespace std;

class MinStack {
    stack<pair<long long, long long>> st; // {val, current_min}
public:
    void push(long long x) {
        long long cur_min = st.empty() ? x : min(x, st.top().second);
        st.push({x, cur_min});
    }
    void pop() { st.pop(); }
    long long top() const { return st.top().first; }
    long long getMin() const { return st.top().second; }
};

class MyQueue {
    stack<long long> in_st, out_st;
    void transfer() {
        if (out_st.empty()) {
            while (!in_st.empty()) {
                out_st.push(in_st.top());
                in_st.pop();
            }
        }
    }
public:
    void push(long long x) { in_st.push(x); }
    long long pop() {
        transfer();
        long long v = out_st.top();
        out_st.pop();
        return v;
    }
    long long peek() {
        transfer();
        return out_st.top();
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    if (!(cin >> q)) {
        MinStack ms;
        ms.push(-2);
        ms.push(0);
        ms.push(-3);
        long long a = ms.getMin();
        ms.pop();
        long long b = ms.top();
        long long c = ms.getMin();
        cout << a << " " << b << " " << c << "\n";
        return 0;
    }
    MinStack ms;
    MyQueue mq;
    vector<long long> outs;
    for (int i = 0; i < q; i++) {
        string op;
        cin >> op;
        if (op == "MPUSH") {
            long long x; cin >> x; ms.push(x);
        } else if (op == "MPOP") {
            ms.pop();
        } else if (op == "MTOP") {
            outs.push_back(ms.top());
        } else if (op == "MMIN") {
            outs.push_back(ms.getMin());
        } else if (op == "QPUSH") {
            long long x; cin >> x; mq.push(x);
        } else if (op == "QPOP") {
            outs.push_back(mq.pop());
        } else if (op == "QPEEK") {
            outs.push_back(mq.peek());
        }
    }
    for (size_t i = 0; i < outs.size(); i++) {
        if (i) cout << " ";
        cout << outs[i];
    }
    cout << "\n";
    return 0;
}

Các lỗi kinh điển trong phỏng vấn và cách tự kiểm chứng

  1. Đổ dữ liệu từ in_st sang out_st khi out_st chưa rỗng: Ở Bước 4 và Bước 5 của bảng chạy tay thứ hai, nếu ngay khi push(30) hoặc trước khi pop() mà bạn vẫn đổ 30 từ in_st sang out_st (trong lúc out_st đang chứa [20, 10]), thì 30 sẽ đè lên đỉnh của out_st và bị lấy ra trước cả 10 lẫn 20! Điều kiện tiên quyết if (out_st.empty()) trong hàm transfer() là bất biến sống còn của thuật toán.
  2. Dùng dấu \(\lt\) thay vì \(\le\) khi cài đặt Min Stack bằng hai ngăn xếp rời: Nếu bạn tách riêng ngăn xếp chính st và ngăn xếp phụ min_st, giả sử chuỗi đẩy vào là push(2), push(1), push(1). Nếu chỉ đẩy vào min_st khi \(x \lt \text{min\_st.top()}\), số 1 thứ hai sẽ bị bỏ qua. Đến khi gọi pop() một lần để lấy số 1 thứ hai ra, bạn thấy st.top() == min_st.top() == 1 nên xóa luôn số 1 duy nhất trong min_st, làm giá trị nhỏ nhất nhảy sai về 2 dù trong st vẫn còn một số 1. Lưu trực tiếp cặp (val, cur_min) như trong code mẫu giúp tránh hoàn toàn bẫy này.
  3. Mẹo tối ưu hóa \(O(1)\) bộ nhớ phụ bằng kỹ thuật lưu hiệu số (khi phỏng vấn nâng cao): Nếu người phỏng vấn cấm dùng thêm bộ nhớ \(O(n)\) cho cur_min, ta có thể lưu hiệu số \(d = x - \text{min\_val}\) vào ngăn xếp (cần dùng kiểu số nguyên 64-bit long long để tránh tràn số khi trừ số âm cho số dương). Nếu \(d \lt 0\), điều đó báo hiệu phần tử vừa đẩy vào nhỏ hơn min_val cũ, ta cập nhật min_val = x; khi pop() gặp đỉnh âm \(d \lt 0\), ta khôi phục min_val cũ bằng công thức \(\text{min\_val\_cũ} = \text{min\_val\_hiện\_tại} - d\).
  4. Cách tự kiểm chứng tại nhà: Để tự kiểm tra lớp MinStack và MyQueue, bạn có thể đối chiếu đầu ra của chúng với một mảng động chuẩn (std::vector kết hợp *std::min_element cho Min Stack, và std::deque chuẩn cho Queue) trên chuỗi thao tác ngẫu nhiên gồm các giá trị trùng nhau (ví dụ miền giá trị chỉ gồm \(\{-1, 0, 1\}\)) và xen kẽ liên tục các đợt push - pop đến khi cấu trúc rỗng hoàn toàn rồi lại push tiếp.

Luyện ngay trên Big-O Coding

Sau khi nắm vững bất biến trạng thái của ngăn xếp lưu cực trị và cơ chế đảo chiều bằng hai ngăn xếp, bạn hãy luyện tập ngay bài toán Min Stack cùng các bài toán biến đổi biểu thức trên ngăn xếp trong lộ trình Coding Interview 150:

Có thể kết hợp cả hai ý tưởng trên để thiết kế Hàng đợi lấy giá trị nhỏ nhất (Min Queue) trong \(O(1)\) khấu hao không?

Hoàn toàn được, và đây chính là câu hỏi mở rộng rất hay gặp ở cuối buổi phỏng vấn! Khi cài đặt hàng đợi bằng hai ngăn xếp in_st và out_st, nếu ta nâng cấp cả in_st lẫn out_st thành hai Min Stack (mỗi phần tử trong cả hai ngăn xếp đều lưu cặp (val, cur_min) của riêng ngăn xếp đó), thì giá trị nhỏ nhất của toàn bộ hàng đợi tại mọi thời điểm chính là \(\min(\text{in\_st.getMin()}, \text{out\_st.getMin()})\). Mọi thao tác thêm vào cuối hàng, lấy ra ở đầu hàng và truy vấn cực tiểu của cửa sổ đều đạt \(O(1)\) khấu hao.

Ngược lại, làm sao cài đặt một Ngăn xếp (LIFO) chỉ bằng Hàng đợi (FIFO)?

Khác với việc dùng hai ngăn xếp tạo ra hàng đợi đạt \(O(1)\) khấu hao nhờ tính chất đảo chiều của ngăn xếp, thao tác đổ dữ liệu giữa hai hàng đợi FIFO không làm đảo ngược thứ tự phần tử (phần tử đầu hàng đợi 1 đổ sang hàng đợi 2 vẫn đứng đầu hàng đợi 2). Vì vậy, để cài đặt Ngăn xếp bằng Hàng đợi (LeetCode 225), ta chỉ cần dùng một hàng đợi duy nhất q: mỗi khi đẩy phần tử mới x vào cuối hàng (q.push(x)), ta lặp \(|q| - 1\) lần thao tác rút phần tử đầu hàng đưa xuống cuối hàng (q.push(q.front()); q.pop()). Khi đó x vươn lên đứng đầu hàng đợi, giúp pop() và top() chạy trong \(O(1)\), còn push(x) tốn \(O(n)\).

Trong hệ thống thời gian thực (Real-time System), hàng đợi bằng hai ngăn xếp có nhược điểm gì?

Mặc dù chi phí trung bình khấu hao của hàng đợi hai ngăn xếp là \(O(1)\), độ trễ đuôi (tail latency / p99 latency) của một lệnh pop() đơn lẻ khi out_st vừa cạn có thể vọt lên \(O(n)\) do phải chép dồn toàn bộ \(n\) phần tử từ in_st sang out_st. Trong các hệ thống thời gian thực yêu cầu độ trễ mỗi lệnh bị chặn trên nghiêm ngặt (worst-case \(O(1)\)), người ta dùng danh sách liên kết hoặc bộ đệm vòng (circular buffer) thay vì hai ngăn xếp.

Muốn học bài bản cùng giảng viên?

Luyện LeetCode thực chiến theo pattern, giải bài trong 45 phút và mock interview cùng AI. 16 buổi online, lớp 7–12 học viên, chọn C++, Java hoặc Python.

Xem Khóa LeetCode

Nguồn tham khảo

Chia sẻ: Facebook LinkedIn
Nhắn Zalo tư vấnZalo Gọi 0937 401 483