Monotonic Stack and Queue

INgăn xếp và dãy ngoặc đúng

Ngăn xếp là một dãy chỉ được thêm và bớt phần tử ở một đầu, gọi là đỉnh: phần tử vào sau cùng được lấy ra trước tiên, giống một chồng đĩa. Thư viện chuẩn có sẵn stack với ba thao tác push (đẩy vào), top (xem đỉnh), pop (bỏ đỉnh). Trong thi đấu, người ta thường dùng luôn vector với push_back, back, pop_back, hoặc string khi phần tử là ký tự, vì viết gọn hơn và cũng nhanh hơn. Cả ba thao tác đều $O(1)$.

Cần cẩn thận hai điều. Gọi top() hay pop() khi ngăn xếp rỗng không báo lỗi mà làm chương trình chạy sai một cách khó đoán, nên luôn kiểm tra empty() trước. Và pop() không trả về giá trị: muốn lấy đỉnh ra dùng thì đọc top() trước rồi mới pop().

Bài toán quen thuộc nhất của ngăn xếp là kiểm tra dãy ngoặc. Cho một xâu chỉ gồm các ký tự (, ), [, ], {, }. Xâu được gọi là dãy ngoặc đúng nếu có thể ghép mỗi ngoặc mở với một ngoặc đóng cùng loại đứng sau nó, sao cho hai cặp bất kỳ hoặc nằm rời nhau, hoặc cặp này nằm trọn trong cặp kia. Chẳng hạn ([]{}) là dãy ngoặc đúng; còn (() thiếu một ngoặc đóng, và ([)] có hai cặp cắt nhau nên đều không đúng.

Cách dễ nghĩ ra nhất là lặp lại việc xóa các cặp (), [], {} đứng liền nhau cho tới khi không xóa được nữa; xâu là dãy ngoặc đúng khi xóa được hết. Mỗi lượt quét tốn $O(n)$ và có thể cần tới $n/2$ lượt, nên cả cách làm là $O(n^2)$.

Ta có thể thấy được điểm lãng phí của cách làm trên: sau khi xóa một cặp, chỉ có ký tự ngay trước cặp đó và ký tự ngay sau cặp đó là mới đứng cạnh nhau, nên cặp mới chỉ có thể xuất hiện ở đúng chỗ ấy. Vì vậy ta chỉ cần duyệt xâu một lần từ trái sang phải và giữ trong ngăn xếp các ngoặc mở chưa được đóng. Gặp ngoặc mở thì đẩy vào. Gặp ngoặc đóng thì ngoặc mở trong cùng chưa được đóng, tức là đỉnh ngăn xếp, phải cùng loại với nó; nếu đúng thì bỏ đỉnh, nếu sai hoặc ngăn xếp rỗng thì xâu không đúng. Duyệt hết xâu mà ngăn xếp vẫn còn ngoặc mở thì xâu cũng không đúng.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
string s, st;

bool ok() {
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') st += c;
        else {
            if (st.empty()) return false;
            char o = st.back();
            st.pop_back();
            if ((c == ')' && o != '(') || (c == ']' && o != '[') || (c == '}' && o != '{')) return false;
        }
    }
    return st.empty();
}

signed main() {
    cin >> s;
    cout << (ok() ? "YES" : "NO") << '\n';
}

ChạyInput([]{})

OutputYES

Độ phức tạp: $O(n)$, với xâu dài $10^6$ cần khoảng $10^6$ phép tính.

Khi xâu chỉ có một loại ngoặc, ngăn xếp chỉ chứa toàn ngoặc (, nên không cần lưu cả ngăn xếp mà chỉ cần đếm số ngoặc đang mở: gặp ( thì tăng, gặp ) thì giảm. Xâu đúng khi số đếm không bao giờ âm và cuối cùng bằng $0$.

Cùng khuôn “giữ những gì còn mở, xử lý ngay khi đỉnh thay đổi” còn giải được nhiều bài xử lý xâu, như ví dụ dưới đây.

Ví dụXóa Mẫu ABC

Đề. Cho xâu $S$ dài không quá $2 \cdot 10^5$, chỉ gồm các chữ A, B, C. Chừng nào $S$ còn chứa xâu con ABC, xóa lần xuất hiện đứng trái nhất của nó. In xâu cuối cùng.

Lời giải. Tìm lại từ đầu sau mỗi lần xóa là $O(n^2)$. Giống bài dãy ngoặc, sau một lần xóa chỉ có phần đứng trước và phần đứng sau là mới nối vào nhau, nên mẫu mới chỉ có thể xuất hiện ngay tại chỗ nối. Ta dùng một ngăn xếp các ký tự được giữ lại: đẩy lần lượt từng ký tự vào, và sau mỗi lần đẩy, nếu ba ký tự trên đỉnh là ABC thì bỏ cả ba. Mẫu luôn bị xóa ngay khi nó vừa hoàn chỉnh, nên đó cũng chính là lần xuất hiện trái nhất. Mỗi ký tự vào và ra nhiều nhất một lần.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
string s, st;

signed main() {
    cin >> s;
    for (char c : s) {
        st += c;
        ll m = st.size();
        if (m >= 3 && st[m - 3] == 'A' && st[m - 2] == 'B' && st[m - 1] == 'C') st.resize(m - 3);
    }
    cout << st << '\n';
}

ChạyInputAABCABCBA

OutputABA

Độ phức tạp: $O(n)$, với $n = 2 \cdot 10^5$ cần khoảng $4 \cdot 10^5$ phép tính.

IIVị trí nhỏ hơn gần nhất

Trở lại bài toán ở đầu bài: với mỗi vị trí $i$, tìm vị trí $j < i$ lớn nhất có $a_j < a_i$; nếu không có thì đáp án là $0$. Cách ngây thơ là với mỗi $i$, đi lùi từ $i - 1$ cho tới khi gặp một số nhỏ hơn $a_i$.

for (ll i = 1; i <= n; i++) {
    ll j = i - 1;
    while (j >= 1 && a[j] >= a[i]) j--;
    ans[i] = j;
}

Độ phức tạp: $O(n^2)$, với dãy giảm dần $n = 2 \cdot 10^5$ cần khoảng $2 \cdot 10^{10}$ phép tính.

Ta có thể thấy được điểm lãng phí của cách làm trên. Giả sử có hai vị trí $j < k$ với $a_j \ge a_k$. Với mọi vị trí $i$ đứng sau $k$, nếu $a_j < a_i$ thì cũng có $a_k \le a_j < a_i$, mà $k$ lại gần $i$ hơn $j$. Vậy từ lúc đi qua $k$, vị trí $j$ không bao giờ còn là đáp án của ai nữa, nhưng cách làm trên vẫn đi lùi qua nó mỗi lần.

Ta chỉ giữ lại những vị trí còn có thể là đáp án, gọi là các ứng viên, trong một ngăn xếp theo thứ tự từ trái sang phải. Khi xét tới $i$:

1. Bỏ khỏi đỉnh mọi ứng viên có giá trị lớn hơn hoặc bằng $a_i$: theo nhận xét trên, từ nay chúng không còn là đáp án của ai.
2. Nếu ngăn xếp rỗng thì đáp án của $i$ là $0$; nếu không thì đáp án là ứng viên đang ở đỉnh.
3. Đẩy $i$ vào ngăn xếp, vì $i$ có thể là đáp án của những vị trí phía sau.

Sau bước 1, mọi ứng viên còn lại đều nhỏ hơn $a_i$; rồi $i$ được đẩy lên trên chúng. Vì vậy giá trị trong ngăn xếp luôn tăng dần từ đáy lên đỉnh. Hình dưới chạy tay trên dãy $6, 2, 5, 5, 1, 4, 3, 7, 2$:

Ở bước $i = 4$, số $5$ ở đỉnh không nhỏ hơn $a_4 = 5$ nên bị bỏ, và đáp án là vị trí $2$ (số $2$). Ở bước $i = 5$, số $1$ nhỏ hơn mọi ứng viên nên cả ngăn xếp bị bỏ hết, đáp án là $0$. Nối mỗi vị trí với đáp án của nó, ta được:

Cũng như vòng while của hai con trỏ ở bài 0.7, vòng lặp bỏ đỉnh có thể chạy nhiều lần ở một bước, nhưng cộng trên cả chương trình thì không quá $n$ lần.

Ví dụChỉ Số Nhỏ Hơn Gần Nhất

Đề. Cho dãy $n \le 2 \cdot 10^5$ số $a_i \le 10^9$. Với mỗi vị trí $i$, in chỉ số $j < i$ lớn nhất có $a_j < a_i$, hoặc $0$ nếu không có.

Lời giải. Đúng thuật toán vừa trình bày. Ngăn xếp lưu chỉ số chứ không lưu giá trị, vì đề hỏi chỉ số; giá trị thì đọc lại qua mảng $a$.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 2e5 + 5;
ll n, a[N];
vector<ll> st;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (ll i = 1; i <= n; i++) cin >> a[i];
    for (ll i = 1; i <= n; i++) {
        while (!st.empty() && a[st.back()] >= a[i]) st.pop_back();
        cout << (st.empty() ? 0 : st.back()) << ' ';
        st.push_back(i);
    }
    cout << '\n';
}

ChạyInput9
6 2 5 5 1 4 3 7 2

Output0 0 2 2 0 5 5 7 5 

Độ phức tạp: $O(n)$, với $n = 2 \cdot 10^5$ cần khoảng $4 \cdot 10^5$ phép tính.

Bài toán có bốn dạng hay gặp, đều chỉ khác điều kiện bỏ đỉnh và chiều duyệt:

• Nhỏ hơn gần nhất bên trái: duyệt từ trái sang, bỏ đỉnh khi a[st.back()] >= a[i].
• Nhỏ hơn hoặc bằng gần nhất bên trái: bỏ đỉnh khi a[st.back()] > a[i].
• Lớn hơn gần nhất bên trái: bỏ đỉnh khi a[st.back()] <= a[i], ngăn xếp khi đó giảm dần.
• Bên phải: làm y hệt nhưng duyệt từ phải sang trái.

Một cách nhớ cho khỏi nhầm: điều kiện bỏ đỉnh là phủ định của điều kiện “là đáp án”. Đáp án cần nhỏ hơn hẳn $a_i$, nên ta bỏ các đỉnh lớn hơn hoặc bằng $a_i$.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 2e5 + 5;
ll n, a[N];
vector<ll> st;

signed main() {
    cin >> n;
    for (ll i = 1; i <= n; i++) cin >> a[i];
    for (ll i = 1; i <= n; i++) {
        while (!st.empty() && a[st.back()] > a[i]) st.pop_back();
        cout << (st.empty() ? 0 : st.back()) << ' ';
        st.push_back(i);
    }
    cout << '\n';
}

ChạyInput3
3 3 3

Output0 1 2 

IIIHình chữ nhật lớn nhất dưới biểu đồ cột

Bài toán: có $n$ cột đứng liền nhau, mỗi cột rộng $1$, cột $i$ cao $h_i$. Tìm diện tích lớn nhất của một hình chữ nhật nằm trọn trong vùng các cột. Thử mọi cặp cột trái và phải rồi lấy chiều cao bằng cột thấp nhất ở giữa tốn $O(n^2)$.

Xét một hình chữ nhật lớn nhất. Chiều cao của nó bằng chiều cao của cột thấp nhất mà nó phủ, gọi là cột $i$; nếu thấp hơn thì nâng lên được. Hình đó cũng không thể kéo rộng thêm, nên hai bên nó là hai cột thấp hơn $h_i$, hoặc là hai đầu dãy. Gọi $L_i$ là vị trí gần nhất bên trái có $h < h_i$ (bằng $0$ nếu không có) và $R_i$ là vị trí gần nhất bên phải có $h < h_i$ (bằng $n + 1$ nếu không có). Khi đó hình chữ nhật lấy cột $i$ làm cột thấp nhất và rộng nhất có thể là

Đáp án là giá trị lớn nhất của biểu thức này qua mọi $i$. Cả $L_i$ lẫn $R_i$ đều là vị trí nhỏ hơn gần nhất ở mục trên, tính bằng hai lượt ngăn xếp: một lượt từ trái sang, một lượt từ phải sang.

Với biểu đồ $2, 1, 4, 5, 1, 3, 3$ ở hình trên, cột $3$ cao $4$ có $L_3 = 2$ và $R_3 = 5$, cho hình rộng $2$, diện tích $8$. Hai cột cuối cùng cao $3$ cho hình rộng $2$ (viền xanh), diện tích $6$.

Ví dụHình Chữ Nhật Dưới Đường Cột

Đề. Biểu đồ có $N \le 10^5$ cột, cột $i$ cao $h_i \le 10^9$. Tìm diện tích lớn nhất của hình chữ nhật nằm trong biểu đồ.

Lời giải. Tính $L_i$ bằng một lượt ngăn xếp từ trái sang, $R_i$ bằng một lượt từ phải sang, rồi lấy giá trị lớn nhất của $h_i (R_i - L_i - 1)$. Khi có nhiều cột cao bằng nhau, cả hai phía đều dùng điều kiện nhỏ hơn hẳn, nên các cột bằng nhau cùng mở rộng qua nhau và cho cùng một hình; tính trùng một hình nhiều lần không ảnh hưởng tới giá trị lớn nhất. Diện tích có thể tới $10^{9} \cdot 10^5 = 10^{14}$, nên cần kiểu long long.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 1e5 + 5;
ll n, h[N], lf[N], rg[N];
vector<ll> st;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (ll i = 1; i <= n; i++) cin >> h[i];
    for (ll i = 1; i <= n; i++) {
        while (!st.empty() && h[st.back()] >= h[i]) st.pop_back();
        lf[i] = st.empty() ? 0 : st.back();
        st.push_back(i);
    }
    st.clear();
    for (ll i = n; i >= 1; i--) {
        while (!st.empty() && h[st.back()] >= h[i]) st.pop_back();
        rg[i] = st.empty() ? n + 1 : st.back();
        st.push_back(i);
    }
    ll ans = 0;
    for (ll i = 1; i <= n; i++) ans = max(ans, h[i] * (rg[i] - lf[i] - 1));
    cout << ans << '\n';
}

ChạyInput7
2
1
4
5
1
3
3

Output8

Độ phức tạp: $O(n)$, với $n = 10^5$ cần khoảng $5 \cdot 10^5$ phép tính.

IVTổng phần tử nhỏ nhất của mọi đoạn

Bài toán: cho dãy $a_1, \dots, a_n$ với $n \le 2 \cdot 10^5$ và $1 \le a_i \le 10^6$, tính tổng giá trị nhỏ nhất của tất cả $\frac{n(n+1)}{2}$ đoạn con. Duyệt mọi đầu trái rồi kéo đầu phải, vừa kéo vừa cập nhật số nhỏ nhất, tốn $O(n^2)$.

Thay vì hỏi “đoạn này có số nhỏ nhất là bao nhiêu”, ta hỏi ngược lại: “số $a_i$ là số nhỏ nhất của bao nhiêu đoạn”. Cách đếm này gọi là đếm đóng góp của từng phần tử. Theo cách đặt $L_i$, $R_i$ như mục trước, $a_i$ là số nhỏ nhất của đoạn $[l, r]$ khi đoạn chứa $i$ và không chứa vị trí nào nhỏ hơn $a_i$, tức là $L_i < l \le i$ và $i \le r < R_i$. Có $i - L_i$ cách chọn $l$ và $R_i - i$ cách chọn $r$, nên

Cần cẩn thận khi dãy có các số bằng nhau. Một đoạn có hai vị trí cùng đạt giá trị nhỏ nhất sẽ được cả hai vị trí đếm, tức là bị cộng hai lần. Cách sửa quen thuộc là cho một phía dùng “nhỏ hơn hẳn”, phía kia dùng “nhỏ hơn hoặc bằng”: $L_i$ là vị trí gần nhất bên trái có giá trị nhỏ hơn $a_i$, còn $R_i$ là vị trí gần nhất bên phải có giá trị nhỏ hơn hoặc bằng $a_i$. Khi đó mỗi đoạn chỉ được đếm cho vị trí đạt giá trị nhỏ nhất đứng xa nhất về bên phải trong đoạn.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 2e5 + 5;
ll n, a[N], lf[N], rg[N];
vector<ll> st;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (ll i = 1; i <= n; i++) cin >> a[i];
    for (ll i = 1; i <= n; i++) {
        while (!st.empty() && a[st.back()] >= a[i]) st.pop_back();
        lf[i] = st.empty() ? 0 : st.back();
        st.push_back(i);
    }
    st.clear();
    for (ll i = n; i >= 1; i--) {
        while (!st.empty() && a[st.back()] > a[i]) st.pop_back();
        rg[i] = st.empty() ? n + 1 : st.back();
        st.push_back(i);
    }
    ll ans = 0;
    for (ll i = 1; i <= n; i++) ans += a[i] * (i - lf[i]) * (rg[i] - i);
    cout << ans << '\n';
}

ChạyInput4
3 1 2 4

Output17

Độ phức tạp: $O(n)$, với $n = 2 \cdot 10^5$ cần khoảng $10^6$ phép tính.

Có khoảng $2 \cdot 10^{10}$ đoạn, nên tổng có thể tới $10^6 \cdot 2 \cdot 10^{10} = 2 \cdot 10^{16}$, vẫn vừa kiểu long long. Khi giá trị lớn hơn nữa, tổng vượt giới hạn của long long và đề thường yêu cầu lấy theo modulo.

Với dãy $3, 1, 2, 4$: số $1$ ở vị trí $2$ là số nhỏ nhất của $2 \cdot 3 = 6$ đoạn, đóng góp $6$; số $3$, $2$, $4$ lần lượt đóng góp $3 \cdot 1 \cdot 1$, $2 \cdot 1 \cdot 2$, $4 \cdot 1 \cdot 1$; tổng là $6 + 3 + 4 + 4 = 17$.

Sử dụng kiến thức này cũng có thể giải bài: với mỗi độ dài $k$ từ $1$ tới $n$, tìm giá trị lớn nhất trong các số nhỏ nhất của mọi đoạn dài $k$. Số $a_i$ là số nhỏ nhất của một đoạn dài tới $R_i - L_i - 1$, nên nó là ứng viên cho mọi độ dài không quá con số đó.

VHàng đợi đơn điệu: lớn nhất trên mọi đoạn trượt

Hàng đợi hai đầu (deque) là dãy cho thêm và bớt phần tử ở cả hai đầu: push_back, pop_back, push_front, pop_front, xem hai đầu bằng front, back, mỗi thao tác $O(1)$. Nó có một cách dùng rất hay gặp.

Bài toán: cho dãy $a_1, \dots, a_n$ và số $k$; với mỗi đoạn gồm $k$ số liền nhau, in số lớn nhất của đoạn. Đoạn này trượt dần sang phải giống cửa sổ ở bài 0.7: mỗi bước thêm một số bên phải và bỏ một số bên trái. Tính lại số lớn nhất của cả đoạn ở mỗi bước tốn $O(k)$, cả dãy $O(nk)$, quá chậm khi $n$ và $k$ cùng lớn.

Ta lại dùng nhận xét như ở mục vị trí nhỏ hơn gần nhất. Nếu $j < r$ và $a_j \le a_r$ thì từ lúc $a_r$ vào đoạn, $a_j$ không bao giờ còn là số lớn nhất của đoạn nào nữa: mọi đoạn chứa $a_j$ về sau cũng chứa $a_r$, vì $a_j$ ra khỏi đoạn trước $a_r$. Vậy ta chỉ giữ các ứng viên, theo thứ tự vị trí, và giá trị của chúng giảm dần. Ứng viên đứng đầu là số lớn nhất của đoạn hiện tại. Mỗi bước:

1. Bỏ ở cuối mọi ứng viên có giá trị không lớn hơn $a_r$, rồi thêm $r$ vào cuối.
2. Bỏ ở đầu ứng viên đã ra khỏi đoạn $[r - k + 1, r]$.

Cách giữ này gọi là hàng đợi đơn điệu (monotonic queue). Ta cần bỏ phần tử ở cả hai đầu, nên dùng deque lưu chỉ số: lưu chỉ số để biết ứng viên đầu đã ra khỏi đoạn hay chưa.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 1e6 + 5;
ll n, k, a[N];
deque<ll> q;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    for (ll i = 1; i <= n; i++) cin >> a[i];
    for (ll r = 1; r <= n; r++) {
        while (!q.empty() && a[q.back()] <= a[r]) q.pop_back();
        q.push_back(r);
        if (q.front() <= r - k) q.pop_front();
        if (r >= k) cout << a[q.front()] << ' ';
    }
    cout << '\n';
}

ChạyInput9 3
4 2 12 3 8 5 7 1 6

Output12 12 12 8 8 7 7 

Độ phức tạp: $O(n)$, với $n = 10^6$ cần khoảng $2 \cdot 10^6$ phép tính.

Mỗi chỉ số vào hàng đợi một lần và ra nhiều nhất một lần, nên cả dãy là $O(n)$ như ngăn xếp đơn điệu. Ở mỗi bước, đoạn chỉ mất đúng một phần tử bên trái, nên chỉ cần một lệnh if để bỏ ở đầu. Muốn số nhỏ nhất thì đổi <= thành >=, khi đó các ứng viên tăng dần.

multiset (bài 0.10.1) cũng làm được: thêm $a_r$, xóa một bản sao của $a_{r-k}$, đọc phần tử lớn nhất. Cách đó viết nhanh hơn, nhưng mỗi bước tốn $O(\log k)$ cùng một lần cấp phát bộ nhớ. Đo trên một triệu số:

Hàng đợi đơn điệu nhanh hơn khoảng 18 lần. Với $n = 2 \cdot 10^5$ thì multiset vẫn chạy kịp; khi $n$ tới $10^6$, hoặc phải làm nhiều lần, nên dùng deque.