Monotonic Stack và Deque

Monotonic Stack (stack đơn điệu) và Monotonic Deque (deque đơn điệu) là kỹ thuật duy trì một dãy phần tử luôn được sắp theo thứ tự tăng (hoặc giảm) trong khi ta duyệt mảng. Nhờ tính đơn điệu này, chúng giải được hàng loạt bài toán cổ điển — phần tử lớn hơn/nhỏ hơn gần nhất, hình chữ nhật lớn nhất trong histogram, cực trị trên cửa sổ trượt, tối ưu quy hoạch động — chỉ trong $O(N)$ thay vì $O(N^2)$ hay $O(NK)$ của cách làm ngây thơ.

Ý tưởng / Trực giác

Câu hỏi cốt lõi: tại sao chỉ giữ một dãy đơn điệu là đủ?

Quan sát "bị che khuất" (monotonic stack). Giả sử ta quét từ trái sang phải và muốn biết, với mỗi $i$, phần tử lớn hơn gần nhất nằm bên phải. Xét hai chỉ số $p<q$ với $a[p]\le a[q]$. Khi đó với mọi chỉ số $r>q$, nếu $a[r]$ đủ lớn để "vượt" $a[p]$ thì nó cũng vượt... nhưng quan trọng hơn: $a[q]$ chắn tầm nhìn của $a[p]$. Một phần tử tương lai muốn làm "next greater" của $p$ thì trước hết phải đi qua $q$, mà $q$ gần $p$ hơn. Vì vậy một khi $a[q]$ xuất hiện và $a[q]\ge a[p]$, phần tử $a[p]$ không bao giờ còn cần đến nữa cho các truy vấn "lớn hơn" về sau — ta có thể pop nó ra. Cái còn lại trong stack luôn là một dãy đơn điệu của những phần tử "chưa bị che".

Mỗi phần tử vào/ra đúng một lần. Đây là chìa khoá độ phức tạp: dù vòng while bên trong trông như lồng nhau, mỗi chỉ số chỉ được push một lần và pop tối đa một lần. Tổng số thao tác $\le 2N$, nên toàn bộ là $O(N)$ — không phải $O(N^2)$ như vẻ ngoài.

Deque đơn điệu = stack đơn điệu + xoá hết hạn ở đầu kia. Khi cửa sổ chỉ rộng $K$, một phần tử có thể "rơi ra khỏi cửa sổ" bên trái. Ta vẫn pop ở đuôi để giữ đơn điệu (giống stack), nhưng thêm thao tác pop ở đầu để loại phần tử đã ra khỏi cửa sổ. Phần tử ở đầu deque luôn là cực trị của cửa sổ hiện tại, vì mọi phần tử "thua kém và cũ hơn" đã bị loại. Vì deque vẫn đơn điệu, đầu deque = max (hoặc min) ngay lập tức trong $O(1)$.

Ví dụ chạy tay

Next Greater Element với monotonic stack

Mảng $a=[2,1,5,3,4]$. Stack lưu chỉ số, giữ cho $a[\text{stack}]$ giảm dần từ đáy lên đỉnh. Khi $a[i]$ lớn hơn đỉnh, đỉnh đó tìm thấy "next greater" là $i$.

i=0  a=2   stack rỗng -> push 0          stack(idx): [0]        a-vals: [2]
i=1  a=1   a[0]=2 > 1, không pop -> push  stack: [0,1]          a-vals: [2,1]
i=2  a=5   a[1]=1<5 -> ans[1]=2, pop 1
           a[0]=2<5 -> ans[0]=2, pop 0
           push 2                         stack: [2]            a-vals: [5]
i=3  a=3   a[2]=5>3 -> push 3             stack: [2,3]          a-vals: [5,3]
i=4  a=4   a[3]=3<4 -> ans[3]=4, pop 3
           a[2]=5>4 -> dừng, push 4       stack: [2,4]          a-vals: [5,4]
hết: các chỉ số còn lại (2,4) không có next greater -> ans = -1

Kết quả ans = [2, 2, -1, 4, -1] (chỉ số của phần tử lớn hơn gần nhất bên phải; $-1$ nếu không có). Để ý chỉ số $1$ (giá trị $1$) bị pop ngay khi gặp $5$ — nó "bị che" đúng như trực giác.

Sliding Window Maximum với monotonic deque

Mảng $a=[1,3,-1,-3,5]$, $K=3$. Deque lưu chỉ số, $a[\text{deque}]$ giảm dần (đầu = max). Ký hiệu F = front, B = back.

i=0 a=1   pop-đuôi: rỗng;  push 0           deque[idx]: [0]      (a: 1)
i=1 a=3   a[0]=1<=3 -> pop 0; push 1        deque:      [1]      (a: 3)
i=2 a=-1  a[1]=3>-1 -> push 2               deque:      [1,2]    (a: 3,-1)
          i>=K-1 -> cửa sổ [0..2], max=a[F=1]=3   --> in 3
i=3 a=-3  front=1, còn trong cửa sổ [1..3]
          a[2]=-1>-3 -> push 3              deque:      [1,2,3]  (a: 3,-1,-3)
          cửa sổ [1..3], max=a[F=1]=3              --> in 3
i=4 a=5   front=1 < i-K+1=2 -> pop-đầu 1    deque:      [2,3]
          a[3]=-3<=5 -> pop 3; a[2]=-1<=5 -> pop 2; push 4
                                            deque:      [4]      (a: 5)
          cửa sổ [2..4], max=a[F=4]=5              --> in 5

Kết quả các cửa sổ: 3 3 5. Đầu deque luôn cho max trong $O(1)$.

Cài đặt

Monotonic stack — Next Greater / Previous Smaller

// Với mỗi i, tìm j > i nhỏ nhất sao cho a[j] > a[i]; -1 nếu không có.
vector<int> next_greater(const vector<int>& a) {
    int n = a.size();
    vector<int> ans(n, -1);
    stack<int> st;                 // lưu CHỈ SỐ; a[st] giảm dần từ đáy lên đỉnh
    for (int i = 0; i < n; i++) {
        // a[i] "vượt" các phần tử nhỏ hơn ở đỉnh -> chúng tìm thấy next greater = i
        while (!st.empty() && a[st.top()] < a[i]) {
            ans[st.top()] = i;
            st.pop();
        }
        st.push(i);
    }
    return ans;
}

// Với mỗi i, tìm j < i lớn nhất sao cho a[j] < a[i]; -1 nếu không có.
vector<int> prev_smaller(const vector<int>& a) {
    int n = a.size();
    vector<int> ans(n, -1);
    stack<int> st;                 // a[st] tăng dần
    for (int i = 0; i < n; i++) {
        // bỏ mọi phần tử >= a[i]: chúng không thể là "smaller" và che tầm nhìn
        while (!st.empty() && a[st.top()] >= a[i]) st.pop();
        if (!st.empty()) ans[i] = st.top();   // đỉnh còn lại là phần tử nhỏ hơn gần nhất
        st.push(i);
    }
    return ans;
}

Largest Rectangle in Histogram

long long largest_rectangle(const vector<int>& h) {
    int n = h.size();
    stack<int> st;                 // chỉ số, h[st] tăng dần
    long long ans = 0;
    for (int i = 0; i <= n; i++) {
        int cur = (i == n) ? 0 : h[i];   // "cột ảo" cao 0 ở cuối để xả hết stack
        while (!st.empty() && h[st.top()] > cur) {
            int height = h[st.top()]; st.pop();
            // chiều rộng = khoảng giữa biên trái mới và i (biên phải)
            int width = st.empty() ? i : i - st.top() - 1;
            ans = max(ans, (long long)height * width);  // CHÚ Ý long long
        }
        st.push(i);
    }
    return ans;
}

Sum of Subarray Minimums

Tính ${\sum }_{l\le r}min(a[l..r])mod({10}^9+7)$. Mỗi $a[i]$ đóng góp với số đoạn con mà nó là phần tử nhỏ nhất; đếm bằng "khoảng bên trái" và "khoảng bên phải".

long long sum_of_minimums(const vector<int>& a) {
    int n = a.size();
    const long long MOD = 1e9 + 7;
    vector<long long> left(n), right(n);
    stack<int> st;
    // left[i]: số phần tử (kể cả i) về bên trái mà a[i] vẫn là min;
    // dùng '>=' để mọi giá trị bằng nhau được đếm về một phía -> tránh đếm trùng.
    for (int i = 0; i < n; i++) {
        while (!st.empty() && a[st.top()] >= a[i]) st.pop();
        left[i] = st.empty() ? i + 1 : i - st.top();
        st.push(i);
    }
    while (!st.empty()) st.pop();
    // right[i]: số phần tử về bên phải; dùng '>' (chặt) để bù với '>=' ở trên.
    for (int i = n - 1; i >= 0; i--) {
        while (!st.empty() && a[st.top()] > a[i]) st.pop();
        right[i] = st.empty() ? n - i : st.top() - i;
        st.push(i);
    }
    long long ans = 0;
    for (int i = 0; i < n; i++)
        ans = (ans + a[i] % MOD * left[i] % MOD * right[i]) % MOD;
    return ans;
}

Monotonic deque — Sliding Window Maximum

vector<int> sliding_window_max(const vector<int>& a, int k) {
    int n = a.size();
    vector<int> ans;
    deque<int> dq;                 // chỉ số, a[dq] giảm dần -> front là max
    for (int i = 0; i < n; i++) {
        // 1) loại phần tử đã ra khỏi cửa sổ ở ĐẦU
        while (!dq.empty() && dq.front() <= i - k) dq.pop_front();
        // 2) loại phần tử nhỏ hơn/bằng a[i] ở ĐUÔI để giữ đơn điệu
        while (!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back();
        dq.push_back(i);
        if (i >= k - 1) ans.push_back(a[dq.front()]);   // front = max cửa sổ
    }
    return ans;
}

DP với cửa sổ trượt (tối ưu $O(NK)\to O(N)$)

Chuyển truy vấn $dp[i]={max}_{i-k\le j<i}dp[j]+\text{cost}[i]$ thành tra cứu $O(1)$ bằng deque đơn điệu giữ $dp$ giảm dần.

deque<int> dq;
dq.push_back(0);                   // dp[0] đã biết
for (int i = 1; i < n; i++) {
    while (!dq.empty() && dq.front() < i - k) dq.pop_front();   // hết hạn cửa sổ
    dp[i] = dp[dq.front()] + cost[i];                           // front = max dp hợp lệ
    while (!dq.empty() && dp[dq.back()] <= dp[i]) dq.pop_back();// giữ đơn điệu
    dq.push_back(i);
}

Độ phức tạp

• Thời gian $O(N)$. Mỗi chỉ số được push đúng một lần và pop tối đa một lần (vào stack/deque rồi ra là biến mất hẳn). Vì vậy tổng số lần lặp của tất cả vòng while cộng lại $\le N$, không phụ thuộc độ sâu từng bước — đây là phân tích khấu hao (amortized). Đừng nhầm vòng while lồng trong for là $O(N^2)$.
• Bộ nhớ $O(N)$. Stack/deque chứa tối đa $N$ chỉ số; các mảng kết quả (ans, left, right) cũng $O(N)$. Với deque cửa sổ trượt thực tế nó không vượt $K$ phần tử cùng lúc, nhưng vẫn ghi $O(N)$ cho an toàn.

⚠️ Lỗi thường gặp

• Tràn số khi nhân chiều cao × chiều rộng / tích nhiều thừa số. Trong histogram, $h_i$ và chiều rộng đều tới ${10}^9$ và ${10}^5$ → tích vượt int (giới hạn ~$2.1\times {10}^9$). Phải ép (long long)height * width. Trong "sum of minimums" phải lấy modulo từng bước (a[i]%MOD*left[i]%MOD*right[i]) vì tích ba số tràn long long nếu không mod.
• Đếm trùng khi có phần tử bằng nhau (tie-breaking). Trong "sum of subarray minimums", nếu cả hai lượt quét đều dùng >= (hoặc đều >), các đoạn có nhiều min bằng nhau sẽ bị đếm hai lần hoặc bị bỏ. Quy ước một bên dùng >=, bên kia dùng > để mỗi đoạn được tính đúng một min đại diện.
• Quên loại phần tử hết hạn ở đầu deque, hoặc sai biên cửa sổ. Với cửa sổ rộng $K$, điều kiện loại đầu phải khớp định nghĩa cửa sổ: nếu cửa sổ là $[i-k+1,i]$ thì pop khi dq.front() <= i - k. Lệch một đơn vị (off-by-one) khiến cửa sổ rộng $K\pm 1$. Cũng chỉ ghi kết quả khi i >= k - 1 (cửa sổ đầu tiên đã đủ phần tử).
• Lưu giá trị thay vì chỉ số. Nếu stack/deque lưu giá trị $a[i]$, bạn mất khả năng tính khoảng cách (chiều rộng histogram) và không biết phần tử có còn trong cửa sổ không. Hầu như luôn lưu chỉ số, truy giá trị qua a[idx].
• Dùng if thay vì while khi pop. Một $a[i]$ lớn có thể "đánh bật" nhiều phần tử ở đỉnh cùng lúc; phải while để pop hết, dùng if chỉ pop một cái sẽ phá vỡ tính đơn điệu và cho kết quả sai.
• Trường hợp biên: mảng rỗng, một phần tử, hoặc $K=N$ / $K=1$. Kiểm tra st.empty() / dq.empty() trước khi gọi .top() / .front(), nếu không sẽ truy cập phần tử không tồn tại (undefined behavior). Trong histogram, "cột ảo" cao $0$ ở cuối (i == n) là mẹo để xả hết stack mà không cần vòng dọn riêng.

Biến thể / Mở rộng

• Stack giảm dần vs tăng dần. Đảo chiều bất đẳng thức khi pop để chuyển giữa "next greater / smaller" và "previous greater / smaller". Bốn biến thể đều cùng một khung.
• Cực tiểu cửa sổ trượt: đổi deque thành tăng dần (a[dq.back()] >= a[i] thì pop) thì đầu deque là min.
• Liên hệ. Monotonic deque là một dạng của kỹ thuật cửa sổ trượt (sliding window); khi dùng để tối ưu DP nó thuộc nhóm tối ưu quy hoạch động. Convex Hull Trick / Li Chao Tree là bước tiến tiếp theo khi hệ số cửa sổ thay đổi tuyến tính.

Tổng kết

Bài tập luyện

• Cửa Sổ Phép Thuật (slidewin) — (Trung cấp) Cực tiểu và cực đại trên mọi cửa sổ rộng $K$ với $N\le {10}^6$ — bài chuẩn để cài deque đơn điệu (cả hai chiều).
• Khu Vực Đọc Sách Hogwarts (histrect) — (Nâng cao) Hình chữ nhật lớn nhất trong histogram bằng monotonic stack; luyện tính biên trái/phải và chú ý tràn số.
• Bức Ảnh (Gold) (photogold) — (Kỳ cựu) Tối đa số vị trí đánh dấu dưới ràng buộc "mỗi đoạn đúng một"; quy về DP tối ưu bằng deque đơn điệu trên cửa sổ.
• Vũ Điệu Cầu Thang Hogwarts (gridwaltz) — (Kỳ cựu) DP trên lưới với chuyển trạng thái cực trị trong cửa sổ — tăng tốc từ $O(NK)$ xuống $O(N)$ bằng monotonic deque.
• Trao Đổi Sữa (Gold) (milkexg) — (Kỳ cựu) Bài khó kết hợp monotonic stack với lập luận toán học, củng cố trực giác "phần tử bị che khuất".