Bài 25: Ngăn xếp đơn điệu và hàng đợi đơn điệu trong C++ và Python: phần tử lớn hơn gần nhất, min/max trên cửa sổ trượt, hình chữ nhật lớn nhất

Series: Thuật toán nâng cao Độ khó: Trung bình Bài 25 / Thuật toán nâng cao Ngăn xếp Deque

// Thuật toán nâng cao · Bài 25

Ngăn xếp đơn điệu và hàng đợi đơn điệu

Tìm số lớn hơn gần nhất cho mọi phần tử, max của mọi cửa sổ trượt, hình chữ nhật lớn nhất trong biểu đồ cột: ba bài tưởng phải $O(n^2)$ nhưng chỉ cần $O(n)$ nhờ một ngăn xếp (hay deque) luôn giữ thứ tự.

Lời mở đầu

Ở bài 11 (STL cơ bản) em đã làm quen với stack, queue và deque. Hồi đó chúng chỉ là “cái hộp chứa đồ”: cho vào, lấy ra. Hôm nay ta dùng chúng theo một cách thông minh hơn nhiều: giữ cho các phần tử bên trong luôn tăng dần hoặc giảm dần, và vứt bỏ ngay những phần tử không bao giờ còn có ích nữa. Cấu trúc như vậy gọi là ngăn xếp đơn điệu (monotonic stack) và hàng đợi đơn điệu (monotonic queue).

Kỹ thuật này xuất hiện rất dày trong đề HSG: tìm phần tử lớn hơn gần nhất, đếm số người nhìn thấy nhau trong hàng, diện tích hình chữ nhật lớn nhất, max/min trên đoạn độ dài cố định, và cả tối ưu quy hoạch động từ $O(nk)$ xuống $O(n)$. Code của nó rất ngắn, chỉ vài dòng, nhưng muốn viết đúng thì em phải hiểu thật rõ vì sao được phép bỏ phần tử. Mình sẽ đi chậm, có hình và mô phỏng cho từng ý.

Bài 24Chia để trị, sắp xếp nhanhBài 25Ngăn xếp, hàng đợi đơn điệuBài 26Toán modulo và tổ hợpBài 27Quy hoạch động nâng caoBài 28Xâu: Hash và KMPBài 29Đường đi ngắn nhấtBài 30DSU và cây khungBài 31Fenwick, Segment TreeBài 32Tổng ôn và đề thi thử

Trong bài này bạn sẽ học: ý tưởng phần tử bị che khuất (phần tử nào không bao giờ còn là đáp án thì bỏ đi); dùng ngăn xếp đơn điệu tìm số lớn hơn / nhỏ hơn gần nhất bên trái, bên phải trong $O(n)$ và cách chứng minh “mỗi phần tử vào, ra một lần”; bài hình chữ nhật lớn nhất trong biểu đồ cột; hàng đợi đơn điệu bằng deque để tìm max/min trên mọi cửa sổ độ dài k; tối ưu quy hoạch động $dp_i = a_i + \max(dp_{i-k..i-1})$. Có khung chạy tay, 3 mô phỏng từng bước và 8 bài tập kèm gợi ý.

Lộ trình bài viết, bấm vào từng phần để nhảy tới:

Phần 1Ôn ngăn xếp, dequePhần 2Lớn hơn gần nhấtPhần 3Hình chữ nhật lớn nhấtPhần 4Max trên cửa sổPhần 5Tối ưu QHĐ, tổng kếtBài tập8 bài + gợi ý

Phần 1Ôn lại ngăn xếp, hàng đợi, deque và ý tưởng “bị che khuất”

Nhắc nhanh ba cấu trúc em đã học ở bài 11. Mọi thao tác dưới đây đều tốn $O(1)$:

Cấu trúc	Nguyên tắc	C++	Python
Ngăn xếp (stack)	vào sau, ra trước (LIFO), chỉ thao tác ở đỉnh	stack<int> st; push, pop, top, empty	st = [] append, pop(), st[-1]
Hàng đợi (queue)	vào trước, ra trước (FIFO): vào ở cuối, ra ở đầu	queue<int> q; push, pop, front	deque với append, popleft
Hàng đợi hai đầu (deque)	thêm, bớt được ở cả hai đầu	deque<int> dq; push_back, pop_back, push_front, pop_front, front, back	from collections import deque; append, pop, appendleft, popleft, dq[0], dq[-1]

Bảng 1. Ba cấu trúc dữ liệu dùng trong bài. Trong Python không dùng list.pop(0) làm hàng đợi vì nó tốn $O(n)$; luôn dùng collections.deque.

Bài toán mở màn. Cho dãy $a_0, a_1, \ldots, a_{n-1}$. Với mỗi $i$, tìm số lớn hơn gần nhất bên phải: số $a_j$ đầu tiên với $j > i$ và $a_j > a_i$ (không có thì in $-1$). Hãy tưởng tượng mỗi số là một cột nhà cao $a_i$, người đứng trên nóc mỗi cột nhìn sang phải: cột đầu tiên chắn tầm nhìn của họ chính là đáp án.

Hình 1. Dãy 4 9 2 3 7 1 5 8 6. Mũi tên đi từ mỗi cột tới cột cao hơn gần nhất bên phải của nó. Hai cột 9 và 8, 6 (đỏ) không có cột nào cao hơn ở phía sau.

Cách nghĩ đầu tiên: với mỗi $i$ đi sang phải tới khi gặp số lớn hơn. Đúng, nhưng với dãy giảm dần như $10^5, 10^5 - 1, \ldots, 1$ thì mỗi lần phải đi tới tận cuối dãy, tổng cộng $O(n^2)$ phép so sánh.

Xem code C++ / Python: cách trâu $O(n^2)$ tìm số lớn hơn gần nhất bên phải (bấm để mở)

#include <bits/stdc++.h>
using namespace std;

int a[5005];

int main(){
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 0; i < n; i++){
        int ans = -1;
        for(int j = i + 1; j < n; j++)        // đi sang phải tới khi gặp số lớn hơn
            if(a[j] > a[i]){ ans = a[j]; break; }
        cout << ans << " ";
    }
    return 0;
}

n = int(input())
a = list(map(int, input().split()))
res = []
for i in range(n):
    ans = -1
    for j in range(i + 1, n):          # đi sang phải tới khi gặp số lớn hơn
        if a[j] > a[i]:
            ans = a[j]
            break
    res.append(ans)
print(*res)

Ý tưởng “bị che khuất”. Để thấy rõ, xét bài toán ngược chiều: tìm số lớn hơn gần nhất bên trái của mỗi phần tử. Giả sử có $j < k$ mà $a_j \le a_k$. Với mọi vị trí $i > k$ đứng nhìn sang trái, cột $k$ vừa gần hơn vừa cao không kém cột $j$: nếu $a_j > a_i$ thì $a_k > a_i$ luôn, và người ở $i$ sẽ bị cột $k$ chắn tầm nhìn trước khi kịp nhìn tới $j$. Tức là $j$ đã bị $k$ che khuất, không bao giờ còn là đáp án cho ai nữa, và có thể vứt đi vĩnh viễn!

Sau khi vứt hết các phần tử bị che khuất, những phần tử còn lại (theo thứ tự từ trái sang phải) phải có giá trị giảm dần: nếu còn hai phần tử liền nhau mà phần tử sau không nhỏ hơn thì phần tử trước đã bị che. Một dãy luôn giảm dần (hoặc luôn tăng dần) gọi là đơn điệu, và vì ta chỉ thêm, bớt ở cuối dãy nên nó chính là một ngăn xếp. Bài “bên phải” ở Hình 1 cũng dùng đúng ngăn xếp ấy, chỉ là nhìn theo chiều ngược lại, ta sẽ thấy ngay ở phần 2.

Câu hỏi cốt lõi của cả bài

Mỗi khi gặp bài có chữ “gần nhất”, “cửa sổ”, “nhìn thấy”, em tự hỏi: “Phần tử nào chắc chắn không bao giờ còn là đáp án nữa?” Bỏ chúng đi, phần còn lại sẽ có thứ tự đơn điệu. Ngăn xếp đơn điệu khi chỉ cần một đầu, deque đơn điệu khi phần tử còn hết hạn ở đầu kia.

Phần 2Số lớn hơn gần nhất với ngăn xếp đơn điệu

Quay lại bài toán số lớn hơn gần nhất bên phải. Ta duyệt $i$ từ trái sang phải và giữ một ngăn xếp chứa chỉ số các phần tử chưa tìm được đáp án. Khi xét $a_i$:

• Trong khi đỉnh ngăn xếp $t$ có $a_t < a_i$: $a_i$ chính là số lớn hơn gần nhất của $t$. Ghi ans[t] = a[i] và lấy $t$ ra.
• Đẩy $i$ vào ngăn xếp: $a_i$ bắt đầu chờ một số lớn hơn nó.

Vì sao $a_i$ là số lớn hơn gần nhất của $t$, chứ không phải chỉ là một số lớn hơn nào đó? Vì nếu có $j$ nằm giữa $t$ và $i$ mà $a_j > a_t$, thì lúc xét $j$ ta đã lấy $t$ ra rồi, $t$ không thể còn trong ngăn xếp. Cũng vì vậy mà các giá trị trong ngăn xếp từ đáy lên đỉnh không tăng: đỉnh luôn là phần tử nhỏ nhất, nên khi đỉnh đã $\ge a_i$ thì dừng được ngay, không cần nhìn xuống dưới.

i	a[i]	Lấy ra (và ghi đáp án)	Ngăn xếp sau bước này (giá trị)
0	4	–	4
1	9	4 → 9	9
2	2	–	9 2
3	3	2 → 3	9 3
4	7	3 → 7	9 7
5	1	–	9 7 1
6	5	1 → 5	9 7 5
7	8	5 → 8, 7 → 8	9 8
8	6	–	9 8 6 (còn lại: đáp án -1)

Bảng 2. Chạy tay với dãy của Hình 1. Ngăn xếp luôn giảm dần từ đáy lên đỉnh. Ba phần tử còn lại cuối cùng không có số lớn hơn ở bên phải.

Em bấm Tiếp từng bước để thấy ngăn xếp (vẽ thành cột) co giãn thế nào, rồi thử nhập dãy tăng dần, giảm dần, toàn số bằng nhau:

MÔ PHỎNGNgăn xếp đơn điệu tìm số lớn hơn gần nhất bên phảiNhập dãy tối đa 12 số rồi bấm Tiếp / Tự chạy. Ngăn xếp vẽ thành cột, đỉnh ở trên.

Dãy số

ChậmVừaNhanh

phần tử đang xétđang chờ trong ngăn xếpvừa bị lấy rađã có đáp án

C++▶ Chạy tay từng dòng codeNgăn xếp st lưu chỉ số các phần tử chưa có đáp án. Ô vàng: a[i] đang xét, ô xanh dương: đang chờ trong st, ô xanh lá: đã có đáp án.

Dữ liệu vào (stdin) – sửa thoải mái9 4 9 2 3 7 1 5 8 6

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4int a[100005], ans[100005];

5

6int main(){

7 int n;

8 cin >> n;

9 for(int i = 0; i < n; i++){ cin >> a[i]; ans[i] = -1; }

10 stack<int> st;

11 for(int i = 0; i < n; i++){

12 while(!st.empty() && a[st.top()] < a[i]){

13 ans[st.top()] = a[i];

14 st.pop();

15 }

16 st.push(i);

17 }

18 for(int i = 0; i < n; i++) cout << ans[i] << " ";

19 return 0;

20}

ChậmVừaNhanhRất nhanh

Xem code C++ / Python: số lớn hơn gần nhất bên phải bằng ngăn xếp đơn điệu (bấm để mở)

#include <bits/stdc++.h>
using namespace std;

int a[200005], ans[200005];

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n;
    cin >> n;
    for(int i = 0; i < n; i++){ cin >> a[i]; ans[i] = -1; }
    stack<int> st;                              // lưu CHỈ SỐ các phần tử đang chờ
    for(int i = 0; i < n; i++){
        while(!st.empty() && a[st.top()] < a[i]){
            ans[st.top()] = a[i];               // a[i] là số lớn hơn gần nhất của đỉnh
            st.pop();
        }
        st.push(i);
    }
    for(int i = 0; i < n; i++) cout << ans[i] << " ";
    return 0;
}

import sys

data = sys.stdin.read().split()
n = int(data[0])
a = list(map(int, data[1:n + 1]))
ans = [-1] * n
st = []                                 # list dùng làm ngăn xếp, lưu chỉ số
for i in range(n):
    while st and a[st[-1]] < a[i]:
        ans[st.pop()] = a[i]            # a[i] là số lớn hơn gần nhất của đỉnh
    st.append(i)
print(*ans)

Vì sao chỉ $O(n)$ dù có vòng while lồng trong for? Đừng đếm số vòng while của từng $i$ (có lúc nó chạy rất nhiều lần), mà hãy đếm theo từng phần tử: mỗi chỉ số được push đúng một lần và bị pop nhiều nhất một lần. Tổng số lần pop trên cả chương trình không vượt quá $n$, nên tổng số vòng while cộng lại $\le n$, cộng thêm $n$ lần kiểm tra điều kiện bị sai để thoát. Tổng cộng $O(n)$. Cách đánh giá “trung bình trên toàn bộ quá trình” này gọi là phân tích khấu hao (amortized).

Bốn biến thể. Chỉ cần đổi chiều duyệt và dấu so sánh. Với cách viết “đáp án là đỉnh ngăn xếp sau khi lấy ra” (rất tiện khi cần biên trái):

Cần tìm	Duyệt	Lấy ra khi	Đáp án của i	Ngăn xếp (đáy → đỉnh)
lớn hơn gần nhất bên trái	trái → phải	a[top] <= a[i]	đỉnh sau khi lấy	giảm dần
nhỏ hơn gần nhất bên trái	trái → phải	a[top] >= a[i]	đỉnh sau khi lấy	tăng dần
lớn hơn gần nhất bên phải	phải → trái	a[top] <= a[i]	đỉnh sau khi lấy	giảm dần
nhỏ hơn gần nhất bên phải	phải → trái	a[top] >= a[i]	đỉnh sau khi lấy	tăng dần

Bảng 3. Bốn biến thể của ngăn xếp đơn điệu. Muốn “lớn hơn hoặc bằng” thì bỏ dấu bằng ở điều kiện lấy ra (< thay cho <=). Ngăn xếp rỗng nghĩa là không có đáp án.

Khuôn mẫu ngăn xếp đơn điệu

stack<int> st;                       // lưu CHỈ SỐ, không lưu giá trị
for(int i = 0; i < n; i++){
    while(!st.empty() && a[st.top()] <= a[i]) st.pop();   // bỏ phần tử bị che
    L[i] = st.empty() ? -1 : st.top();  // lớn hơn gần nhất bên trái
    st.push(i);
}

Luôn lưu chỉ số: từ chỉ số lấy được cả giá trị lẫn khoảng cách (bài tập 2), còn lưu giá trị thì mất thông tin vị trí.

Cẩn thận dấu bằng

Với dãy có các số bằng nhau, < và <= cho kết quả khác nhau. Em đọc kỹ đề: “lớn hơn” (nghiêm ngặt) hay “không nhỏ hơn”. Mẹo kiểm tra: thử ngay với dãy 3 3 3, đáp án phải đúng như đề yêu cầu.

Phần 3Hình chữ nhật lớn nhất trong biểu đồ cột

Bài toán. Có $n$ cột liền nhau, mỗi cột rộng 1 và cao $h_i$. Tìm diện tích hình chữ nhật lớn nhất nằm gọn trong biểu đồ (các cạnh song song với trục). Đây là bài kinh điển, và là chìa khoá cho bài “ma trận toàn số 1 lớn nhất” (bài tập 8).

Hình 2. Biểu đồ cột 2 1 5 6 2 3. Hình chữ nhật xanh lá cao 5, phủ cột 2 và 3, diện tích 10 là lớn nhất. Hình cam nét đứt cao 1 phủ cả 6 cột chỉ được 6.

Nhận xét quan trọng: hình chữ nhật tối ưu luôn có chiều cao bằng đúng chiều cao của cột thấp nhất mà nó phủ (nếu thấp hơn thì kéo cao lên được). Vậy ta thử lần lượt từng cột $i$ làm “cột thấp nhất”: hình chữ nhật cao $h_i$ sẽ vươn sang trái và sang phải xa nhất có thể, tới khi gặp cột thấp hơn $h_i$. Gọi

• $L_i$ = chỉ số cột thấp hơn gần nhất bên trái ($-1$ nếu không có),
• $R_i$ = chỉ số cột thấp hơn gần nhất bên phải ($n$ nếu không có).

thì hình chữ nhật dựng trên cột $i$ rộng $R_i - L_i - 1$, diện tích $h_i \cdot (R_i - L_i - 1)$. Đáp án là max của $n$ giá trị này. Mà $L_i$, $R_i$ chính là hai biến thể “nhỏ hơn gần nhất” ở Bảng 3!

i	0	1	2	3	4	5
h[i]	2	1	5	6	2	3
L[i]	-1	-1	1	2	1	4
R[i]	1	6	4	4	6	6
rộng	1	6	2	1	4	1
diện tích	2	6	10	6	8	3

Bảng 4. Tính $L_i$, $R_i$ và diện tích cho từng cột của Hình 2. Ví dụ cột 4 cao 2: bên trái gặp cột 1 (cao 1) thấp hơn, bên phải không có cột nào thấp hơn nên $R_4 = 6$; rộng $6 - 1 - 1 = 4$, diện tích 8.

Xem code C++ / Python: hình chữ nhật lớn nhất bằng hai lần ngăn xếp đơn điệu (bấm để mở)

#include <bits/stdc++.h>
using namespace std;

long long h[200005];
int L[200005], R[200005];

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) cin >> h[i];
    stack<int> st;
    for(int i = 0; i < n; i++){                     // L[i]: cột thấp hơn gần nhất bên trái
        while(!st.empty() && h[st.top()] >= h[i]) st.pop();
        L[i] = st.empty() ? -1 : st.top();
        st.push(i);
    }
    while(!st.empty()) st.pop();
    for(int i = n - 1; i >= 0; i--){                // R[i]: cột thấp hơn gần nhất bên phải
        while(!st.empty() && h[st.top()] >= h[i]) st.pop();
        R[i] = st.empty() ? n : st.top();
        st.push(i);
    }
    long long best = 0;
    for(int i = 0; i < n; i++)                      // hình chữ nhật cao đúng h[i]
        best = max(best, h[i] * (R[i] - L[i] - 1));
    cout << best;
    return 0;
}

import sys

data = sys.stdin.read().split()
n = int(data[0])
h = list(map(int, data[1:n + 1]))
L, R, st = [-1] * n, [n] * n, []
for i in range(n):                      # L[i]: cột thấp hơn gần nhất bên trái
    while st and h[st[-1]] >= h[i]:
        st.pop()
    L[i] = st[-1] if st else -1
    st.append(i)
st = []
for i in range(n - 1, -1, -1):          # R[i]: cột thấp hơn gần nhất bên phải
    while st and h[st[-1]] >= h[i]:
        st.pop()
    R[i] = st[-1] if st else n
    st.append(i)
print(max(h[i] * (R[i] - L[i] - 1) for i in range(n)))

Gộp thành một lần duyệt. Để ý: lúc cột $j$ bị lấy ra khỏi ngăn xếp (vì gặp cột $i$ thấp hơn hoặc bằng), ta biết ngay cả hai biên: bên phải là $i$, bên trái là phần tử nằm ngay dưới $j$ trong ngăn xếp. Thêm một cột ảo cao 0 ở cuối để ép mọi cột ra. Khi có các cột bằng nhau, hình tính lúc lấy cột trước ra có thể chưa rộng nhất, nhưng cột bằng nó đứng sau sẽ tính lại hình rộng đúng, nên đáp án cuối vẫn đúng. Mô phỏng dưới đây chạy đúng cách này:

MÔ PHỎNGHình chữ nhật lớn nhất trong biểu đồ cột bằng ngăn xếpNhập tối đa 10 chiều cao (1 đến 9). Hình xanh lá là hình chữ nhật vừa tính, viền cam nét đứt là kỷ lục.

Chiều cao các cột

ChậmVừaNhanh

cột đang xétcột trong ngăn xếpcột vừa lấy rahình chữ nhật vừa tínhđã xử lý xong

Tràn số

Chiều cao tới $10^9$, chiều rộng tới $10^5$ hay $10^6$ thì diện tích tới $10^{15}$: bắt buộc dùng long long cho phép nhân (code trên khai báo h kiểu long long luôn cho chắc).

Phần 4Hàng đợi đơn điệu: max, min trên cửa sổ trượt

Bài toán. Cho dãy $n$ số và số $k$. In ra max của mọi đoạn liên tiếp độ dài $k$: $[0..k-1], [1..k], \ldots, [n-k..n-1]$. Cách trâu tính max từng đoạn mất $O(nk)$, với $n = 10^6$, $k = 5 \cdot 10^5$ là quá chậm. Ở bài 17 (hai con trỏ) em đã trượt cửa sổ để tính tổng rất dễ: thêm số mới, trừ số cũ. Nhưng max thì không trừ được: số lớn nhất ra khỏi cửa sổ rồi thì max mới là ai?

Áp dụng câu hỏi cốt lõi: phần tử nào không bao giờ còn là max nữa? Nếu $j < i$ và $a_j \le a_i$ thì $a_j$ vô dụng: nó rời cửa sổ trước $a_i$, mà trong suốt thời gian còn ở trong cửa sổ, nó luôn có $a_i$ đè lên. Bỏ hết những phần tử như vậy, các ứng viên còn lại có giá trị giảm dần theo thứ tự vị trí. Khác với phần 2, giờ có thêm chuyện phần tử hết hạn ở phía đầu (rơi ra khỏi cửa sổ). Cần bỏ ở cả hai đầu → dùng deque:

1. Thêm $a_i$: trong khi phần tử cuối deque $\le a_i$ thì bỏ nó (giống hệt ngăn xếp đơn điệu), rồi đẩy $i$ vào cuối.
2. Nếu chỉ số ở đầu deque $\le i - k$ thì nó đã ra khỏi cửa sổ, bỏ đi.
3. Khi $i \ge k - 1$: đầu deque là max của cửa sổ $[i-k+1..i]$.

MÔ PHỎNGHàng đợi đơn điệu: max trên mọi cửa sổ độ dài kNhập dãy (tối đa 14 số) và k. Gạch chân cam là cửa sổ hiện tại, hàng Deque là các ứng viên làm max.

Dãy sốk

ChậmVừaNhanh

phần tử mới vàođầu deque = maxứng viên khác trong dequevừa bị bỏngoài cửa sổ

C++▶ Chạy tay từng dòng codeDeque dq lưu chỉ số, a[dq] giảm dần từ đầu tới cuối. Ô trắng: cửa sổ hiện tại, ô xanh lá: đầu deque (max), ô vàng: phần tử mới.

Dữ liệu vào (stdin) – sửa thoải mái8 3 4 2 12 3 8 7 1 5

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4int a[100005];

5

6int main(){

7 int n, k;

8 cin >> n >> k;

9 for(int i = 0; i < n; i++) cin >> a[i];

10 deque<int> dq;

11 for(int i = 0; i < n; i++){

12 while(!dq.empty() && a[dq.back()] <= a[i])

13 dq.pop_back();

14 dq.push_back(i);

15 if(dq.front() <= i - k) dq.pop_front();

16 if(i >= k - 1) cout << a[dq.front()] << " ";

17 }

18 return 0;

19}

ChậmVừaNhanhRất nhanh

Xem code C++ / Python: max trên mọi cửa sổ độ dài k bằng deque (bấm để mở)

#include <bits/stdc++.h>
using namespace std;

int a[1000005];

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    for(int i = 0; i < n; i++) cin >> a[i];
    deque<int> dq;                               // chỉ số, a[dq] giảm dần từ đầu tới cuối
    for(int i = 0; i < n; i++){
        while(!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back();   // bỏ ứng viên vô dụng
        dq.push_back(i);
        if(dq.front() <= i - k) dq.pop_front();  // đầu deque đã ra khỏi cửa sổ
        if(i >= k - 1) cout << a[dq.front()] << " ";
    }
    return 0;
}

import sys
from collections import deque

data = sys.stdin.buffer.read().split()
n, k = int(data[0]), int(data[1])
a = list(map(int, data[2:2 + n]))
dq, res = deque(), []                    # chỉ số, a[dq] giảm dần từ đầu tới cuối
for i in range(n):
    while dq and a[dq[-1]] <= a[i]:      # bỏ ứng viên vô dụng
        dq.pop()
    dq.append(i)
    if dq[0] <= i - k:                   # đầu deque đã ra khỏi cửa sổ
        dq.popleft()
    if i >= k - 1:
        res.append(a[dq[0]])
print(*res)

Độ phức tạp vẫn là $O(n)$ theo đúng lập luận khấu hao ở phần 2: mỗi chỉ số vào deque một lần, ra nhiều nhất một lần (ở đầu hoặc ở cuối). Không phụ thuộc $k$!

Muốn min thay vì max?

Chỉ đổi điều kiện bỏ ở cuối thành a[dq.back()] >= a[i]: deque khi đó tăng dần và đầu deque là min. Muốn cả max lẫn min cùng lúc (bài tập 3, 7) thì dùng hai deque riêng.

Lỗi hay gặp

1. Lưu giá trị vào deque thay vì chỉ số: không biết phần tử ở đầu đã ra khỏi cửa sổ chưa. 2. Gọi dq.front() khi deque rỗng: theo thứ tự ở trên (đẩy $i$ vào trước rồi mới kiểm tra đầu) thì deque luôn có ít nhất phần tử $i$, an toàn. 3. Trong Python dùng list.pop(0) thay cho deque.popleft(): mỗi lần tốn $O(n)$, cả bài thành $O(n^2)$.

Phần 5Ứng dụng: tối ưu quy hoạch động và dấu hiệu nhận dạng

Bài toán nhảy ô. Có $n$ ô xếp thành hàng, ô $i$ ghi điểm $a_i$ (có thể âm). Ếch bắt đầu ở ô 1, phải kết thúc ở ô $n$, mỗi bước nhảy tiến lên từ 1 tới $k$ ô và cộng điểm của ô nó đáp xuống. Tổng điểm (kể cả ô 1) lớn nhất là bao nhiêu? ($n, k \le 10^6$.)

Theo cách học ở bài 19 (quy hoạch động): gọi $dp_i$ là tổng lớn nhất khi đứng ở ô $i$. Ô liền trước $i$ là một ô $j$ trong khoảng $[i-k, i-1]$, nên

$dp_1 = a_1, \qquad dp_i = a_i + \max\left(dp_{i-k}, dp_{i-k+1}, \ldots, dp_{i-1}\right).$

Tính thẳng mất $O(nk)$, tới $10^{12}$ phép tính. Nhưng nhìn kỹ: ta cần max của $k$ giá trị $dp$ đứng ngay trước, mà đoạn $[i-k, i-1]$ trượt sang phải một ô mỗi lần $i$ tăng. Đó chính là max trên cửa sổ trượt của phần 4, chỉ khác ở chỗ dãy $dp$ được tính dần dần: tính xong $dp_i$ thì mới đẩy nó vào deque. Mỗi bước $O(1)$ khấu hao, cả bài $O(n)$.

i	1	2	3	4	5	6
a[i]	1	-2	-3	4	-5	6
max dp cửa sổ	–	dp[1] = 1	dp[1] = 1	dp[2] = -1	dp[4] = 3	dp[4] = 3
dp[i]	1	-1	-2	3	-2	9

Bảng 5. Ví dụ $n = 6$, $k = 2$. Đường đi tốt nhất: ô 1 → 2 → 4 → 6, tổng $1 - 2 + 4 + 6 = 9$.

Xem code C++ / Python: quy hoạch động $dp_i = a_i + \max(dp_{i-k..i-1})$ tối ưu bằng deque (bấm để mở)

#include <bits/stdc++.h>
using namespace std;

long long a[1000005], dp[1000005];

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    for(int i = 1; i <= n; i++) cin >> a[i];
    deque<int> dq;                    // chỉ số j, dp[j] giảm dần từ đầu tới cuối
    dp[1] = a[1];
    dq.push_back(1);
    for(int i = 2; i <= n; i++){
        if(dq.front() < i - k) dq.pop_front();          // j phải >= i - k
        dp[i] = a[i] + dp[dq.front()];                  // max(dp[i-k..i-1]) nằm ở đầu deque
        while(!dq.empty() && dp[dq.back()] <= dp[i]) dq.pop_back();
        dq.push_back(i);
    }
    cout << dp[n];
    return 0;
}

import sys
from collections import deque

data = sys.stdin.buffer.read().split()
n, k = int(data[0]), int(data[1])
a = [0] + list(map(int, data[2:2 + n]))
dp = [0] * (n + 1)
dp[1] = a[1]
dq = deque([1])                         # chỉ số j, dp[j] giảm dần từ đầu tới cuối
for i in range(2, n + 1):
    if dq[0] < i - k:                   # j phải >= i - k
        dq.popleft()
    dp[i] = a[i] + dp[dq[0]]            # max(dp[i-k..i-1]) nằm ở đầu deque
    while dq and dp[dq[-1]] <= dp[i]:
        dq.pop()
    dq.append(i)
print(dp[n])

Tổng kết: khi nào nghĩ tới ngăn xếp, hàng đợi đơn điệu?

Dấu hiệu trong đề	Công cụ	Ví dụ
“gần nhất bên trái/phải mà lớn hơn/nhỏ hơn”, “nhìn thấy”, “bị chắn”	ngăn xếp đơn điệu	bài tập 1, 2
“mỗi phần tử là min/max của bao nhiêu đoạn con”, tổng min/max mọi đoạn	ngăn xếp đơn điệu, tính đóng góp	bài tập 6
hình chữ nhật lớn nhất, ma trận con toàn 1	ngăn xếp đơn điệu trên chiều cao	bài tập 4, 8
xoá bớt phần tử để dãy/số còn lại nhỏ nhất, lớn nhất theo thứ tự từ điển	ngăn xếp đơn điệu + tham lam	bài tập 5
max/min trên đoạn độ dài cố định $k$, hoặc đoạn có hai đầu cùng tiến	deque đơn điệu	bài tập 3, 7
QHĐ dạng $dp_i = f(i) + \max/\min$ của $dp_j$ với $j$ trong cửa sổ trượt	deque đơn điệu	phần 5

Bảng 6. Các dấu hiệu nhận dạng. Điểm chung: phần tử cũ bị phần tử mới “đè” thì không bao giờ còn là đáp án.

So với các công cụ khác

Max trên cửa sổ trượt còn có thể làm bằng multiset hoặc hàng đợi ưu tiên trong $O(n \log n)$, hoặc bảng thưa (sparse table) cho truy vấn đoạn bất kỳ. Deque đơn điệu nhanh nhất ($O(n)$) và ngắn nhất, nhưng chỉ dùng được khi hai đầu đoạn cùng tiến về một phía. Khi các đoạn truy vấn lộn xộn, em sẽ cần cây phân đoạn ở bài 31.

Luyện tập trên web

Các bài dưới đây trên blog đều có lời giải chi tiết bằng C++ và Python, xếp từ dễ tới khó. Em hãy tự làm trước rồi mới xem lời giải nhé.

• Dãy ngoặc đúng (Dễ)
• Di chuyển toa tàu (Dễ)
• Xóa Chữ Số (DELNUM) (Trung bình)
• Nhảy Lò Cò (Trung bình)
• Trò Chơi 2 (DPGAME2) (Trung bình)
• Camera (Khá)

Xem toàn bộ bài cùng chủ đề: nhãn Ngăn xếp.

Bài tậpLuyện ngăn xếp và hàng đợi đơn điệu

Bài 1Số lớn hơn gần nhất bên tráiDễ

Cho dãy $n$ số nguyên dương ($n \le 2 \cdot 10^5$, $a_i \le 10^9$). Với mỗi $i$, in ra giá trị $a_j$ với $j < i$ lớn nhất mà $a_j > a_i$. Nếu không có, in $-1$.

Input

6
3 8 5 2 6 6

Output

-1 -1 8 5 8 8

📝 Nộp bài, chấm tự động trên ClueOJ ↗

💡 Gợi ý

Dòng đầu của Bảng 3: duyệt trái sang phải, lấy ra khỏi ngăn xếp mọi phần tử $\le a_i$ (chúng bị $a_i$ che khuất với mọi phần tử phía sau), lúc đó đỉnh ngăn xếp chính là đáp án, rồi đẩy $a_i$ vào. Ví dụ: tại số 6 cuối cùng, ngăn xếp đang là 8, 6 (của vị trí 4); số 6 kia không lớn hơn 6 nên bị lấy ra, đỉnh còn 8.

Xem code tham khảo (C++ / Python)

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n), st;                 // vector dùng làm ngăn xếp
    for(int &x : a) cin >> x;
    for(int i = 0; i < n; i++){
        while(!st.empty() && st.back() <= a[i]) st.pop_back();   // bị a[i] che khuất
        cout << (st.empty() ? -1 : st.back()) << " ";
        st.push_back(a[i]);
    }
    return 0;
}

import sys

data = sys.stdin.read().split()
n = int(data[0])
a = list(map(int, data[1:n + 1]))
st, res = [], []
for x in a:
    while st and st[-1] <= x:            # bị x che khuất
        st.pop()
    res.append(st[-1] if st else -1)
    st.append(x)
print(*res)

Bài 2Chờ ngày ấm hơnDễ

Bản tin dự báo nhiệt độ $n$ ngày tới: $t_1, t_2, \ldots, t_n$ ($n \le 2 \cdot 10^5$, $-50 \le t_i \le 50$). Với mỗi ngày, cho biết phải chờ thêm bao nhiêu ngày nữa mới có một ngày ấm hơn hẳn. Nếu không có ngày nào như vậy, in 0.

Input

8
23 24 25 21 19 22 26 23

Output

1 1 4 2 1 1 0 0

📝 Nộp bài, chấm tự động trên ClueOJ ↗

💡 Gợi ý

Đúng bài số lớn hơn gần nhất bên phải ở phần 2, nhưng in khoảng cách $j - i$ thay vì giá trị. Đây là lý do ta luôn lưu chỉ số trong ngăn xếp. Ngày 3 (25 độ) phải đợi tới ngày 7 (26 độ), tức 4 ngày.

Xem code tham khảo (C++ / Python)

#include <bits/stdc++.h>
using namespace std;

int t[200005], ans[200005];

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) cin >> t[i];
    stack<int> st;
    for(int i = 0; i < n; i++){
        while(!st.empty() && t[st.top()] < t[i]){
            ans[st.top()] = i - st.top();     // khoảng cách tới ngày ấm hơn
            st.pop();
        }
        st.push(i);
    }
    for(int i = 0; i < n; i++) cout << ans[i] << " ";   // còn trong ngăn xếp: 0
    return 0;
}

import sys

data = sys.stdin.read().split()
n = int(data[0])
t = list(map(int, data[1:n + 1]))
ans, st = [0] * n, []
for i in range(n):
    while st and t[st[-1]] < t[i]:
        j = st.pop()
        ans[j] = i - j                # khoảng cách tới ngày ấm hơn
    st.append(i)
print(*ans)

Bài 3Biên độ nhiệt trong cửa sổTrung bình

Cho dãy $n$ số nguyên ($n \le 5 \cdot 10^5$, $|a_i| \le 10^9$) và số $k$ ($1 \le k \le n$). Với mỗi đoạn liên tiếp độ dài $k$ (từ trái sang phải), in ra hiệu giữa số lớn nhất và số nhỏ nhất của đoạn.

Input

7 3
1 5 2 8 3 3 6

Output

4 6 6 5 3

📝 Nộp bài, chấm tự động trên ClueOJ ↗

💡 Gợi ý

Dùng hai deque cùng lúc: một deque giảm dần cho max, một deque tăng dần cho min (chỉ đổi dấu so sánh, xem mẹo ở phần 4). Các cửa sổ: [1 5 2] → 5 − 1 = 4, [5 2 8] → 6, [2 8 3] → 6, [8 3 3] → 5, [3 3 6] → 3. Hiệu có thể tới $2 \cdot 10^9$, dùng long long.

Xem code tham khảo (C++ / Python)

#include <bits/stdc++.h>
using namespace std;

long long a[500005];

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    for(int i = 0; i < n; i++) cin >> a[i];
    deque<int> mx, mn;                  // mx: a giảm dần, mn: a tăng dần
    for(int i = 0; i < n; i++){
        while(!mx.empty() && a[mx.back()] <= a[i]) mx.pop_back();
        while(!mn.empty() && a[mn.back()] >= a[i]) mn.pop_back();
        mx.push_back(i); mn.push_back(i);
        if(mx.front() <= i - k) mx.pop_front();
        if(mn.front() <= i - k) mn.pop_front();
        if(i >= k - 1) cout << a[mx.front()] - a[mn.front()] << " ";
    }
    return 0;
}

import sys
from collections import deque

data = sys.stdin.buffer.read().split()
n, k = int(data[0]), int(data[1])
a = list(map(int, data[2:2 + n]))
mx, mn, res = deque(), deque(), []      # mx: a giảm dần, mn: a tăng dần
for i in range(n):
    x = a[i]
    while mx and a[mx[-1]] <= x:
        mx.pop()
    while mn and a[mn[-1]] >= x:
        mn.pop()
    mx.append(i); mn.append(i)
    if mx[0] <= i - k:
        mx.popleft()
    if mn[0] <= i - k:
        mn.popleft()
    if i >= k - 1:
        res.append(a[mx[0]] - a[mn[0]])
print(*res)

Bài 4Tấm biển quảng cáoTrung bình

Một dãy $n$ toà nhà liền nhau, toà thứ $i$ rộng 1 mét và cao $h_i$ mét ($n \le 5 \cdot 10^5$, $1 \le h_i \le 10^9$). Người ta muốn dán một tấm biển hình chữ nhật lên mặt trước các toà nhà, cạnh dưới chạm đất, không được nhô ra khỏi toà nào. Tìm diện tích lớn nhất của tấm biển.

Input

7
6 2 5 4 5 1 6

Output

12

📝 Nộp bài, chấm tự động trên ClueOJ ↗

💡 Gợi ý

Chính là bài hình chữ nhật lớn nhất ở phần 3. Với mỗi toà $i$, tìm toà thấp hơn gần nhất bên trái $L_i$ và bên phải $R_i$, diện tích $h_i \cdot (R_i - L_i - 1)$. Trong ví dụ, tấm biển cao 4 phủ ba toà 5 4 5 (vị trí 2 tới 4) được 12. Diện tích tới $5 \cdot 10^{14}$ nên cần long long.

Xem code tham khảo (C++ / Python)

#include <bits/stdc++.h>
using namespace std;

long long h[500005];
int L[500005], R[500005];

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) cin >> h[i];
    stack<int> st;
    for(int i = 0; i < n; i++){                     // L[i]: cột thấp hơn gần nhất bên trái
        while(!st.empty() && h[st.top()] >= h[i]) st.pop();
        L[i] = st.empty() ? -1 : st.top();
        st.push(i);
    }
    while(!st.empty()) st.pop();
    for(int i = n - 1; i >= 0; i--){                // R[i]: cột thấp hơn gần nhất bên phải
        while(!st.empty() && h[st.top()] >= h[i]) st.pop();
        R[i] = st.empty() ? n : st.top();
        st.push(i);
    }
    long long best = 0;
    for(int i = 0; i < n; i++)                      // hình chữ nhật cao đúng h[i]
        best = max(best, h[i] * (R[i] - L[i] - 1));
    cout << best;
    return 0;
}

import sys

data = sys.stdin.read().split()
n = int(data[0])
h = list(map(int, data[1:n + 1]))
L, R, st = [-1] * n, [n] * n, []
for i in range(n):                      # L[i]: cột thấp hơn gần nhất bên trái
    while st and h[st[-1]] >= h[i]:
        st.pop()
    L[i] = st[-1] if st else -1
    st.append(i)
st = []
for i in range(n - 1, -1, -1):          # R[i]: cột thấp hơn gần nhất bên phải
    while st and h[st[-1]] >= h[i]:
        st.pop()
    R[i] = st[-1] if st else n
    st.append(i)
print(max(h[i] * (R[i] - L[i] - 1) for i in range(n)))

Bài 5Xoá k chữ sốTrung bình

Cho một số nguyên dương $S$ có $n$ chữ số ($n \le 2 \cdot 10^5$, có thể có chữ số 0 nhưng chữ số đầu khác 0) và số $k$ ($0 \le k \le n$). Hãy xoá đúng $k$ chữ số của $S$ (giữ nguyên thứ tự các chữ số còn lại) để được số nhỏ nhất. In số đó, bỏ các chữ số 0 ở đầu; nếu không còn chữ số nào hoặc toàn số 0 thì in 0.

Input

1432219 3

Output

1219

📝 Nộp bài, chấm tự động trên ClueOJ ↗

💡 Gợi ý

Tham lam từ trái sang phải: chữ số đứng trước có trọng số lớn hơn, nên nếu chữ số đang xét $d$ nhỏ hơn chữ số ngay trước nó (đỉnh ngăn xếp) và còn quyền xoá thì xoá chữ số trước đi, lặp lại. Ngăn xếp các chữ số giữ lại luôn không giảm. Duyệt hết mà vẫn còn quyền xoá thì xoá ở cuối (các chữ số lớn nhất). Ví dụ: 1, gặp 4 đẩy vào, gặp 3 < 4 xoá 4, gặp 2 < 3 xoá 3, gặp 2 giữ, gặp 1 < 2 xoá 2 (hết 3 lần xoá), giữ nốt 1, 9 → 1219. Bài anh em của nó là xoá để được số lớn nhất (đổi dấu so sánh), có trong phần luyện tập.

Xem code tham khảo (C++ / Python)

#include <bits/stdc++.h>
using namespace std;

int main(){
    string s;
    int k;
    cin >> s >> k;
    string st;                                   // string dùng làm ngăn xếp
    for(char d : s){
        while(k > 0 && !st.empty() && st.back() > d){
            st.pop_back(); k--;                  // xoá chữ số lớn đứng trước
        }
        st.push_back(d);
    }
    while(k > 0 && !st.empty()){ st.pop_back(); k--; }   // còn quyền xoá: xoá ở cuối
    int p = 0;
    while(p < (int)st.size() && st[p] == '0') p++;       // bỏ số 0 ở đầu
    string res = st.substr(p);
    cout << (res.empty() ? "0" : res);
    return 0;
}

s, k = input().split()
k = int(k)
st = []
for d in s:
    while k > 0 and st and st[-1] > d:
        st.pop()                       # xoá chữ số lớn đứng trước
        k -= 1
    st.append(d)
if k > 0:
    st = st[:-k] if k < len(st) else []  # còn quyền xoá: xoá ở cuối
res = ''.join(st).lstrip('0')
print(res if res else '0')

Bài 6Tổng min của mọi đoạn conKhá

Cho dãy $n$ số nguyên dương ($n \le 3 \cdot 10^5$, $a_i \le 10^9$). Tính tổng các giá trị nhỏ nhất của tất cả $\frac{n(n+1)}{2}$ đoạn con liên tiếp, lấy phần dư khi chia cho $10^9 + 7$.

Input

4
3 1 2 4

Output

17

📝 Nộp bài, chấm tự động trên ClueOJ ↗

💡 Gợi ý

Đổi góc nhìn: thay vì duyệt từng đoạn, hỏi $a_i$ là min của bao nhiêu đoạn? Gọi $L_i$ là vị trí số nhỏ hơn hẳn gần nhất bên trái, $R_i$ là vị trí số nhỏ hơn hoặc bằng gần nhất bên phải. Đoạn nhận $a_i$ làm min phải có đầu trái trong $(L_i, i]$ và đầu phải trong $[i, R_i)$: có $(i - L_i)(R_i - i)$ đoạn. Đáp án $= \sum a_i (i - L_i)(R_i - i)$. Một bên dùng dấu nghiêm ngặt, một bên không, để đoạn có nhiều số min bằng nhau chỉ được đếm đúng một lần (cho số min đứng bên phải nhất trong đoạn). Ví dụ: số 1 là min của $2 \cdot 3 = 6$ đoạn, số 3 của 1 đoạn, số 2 của 2 đoạn, số 4 của 1 đoạn: $3 + 6 + 4 + 4 = 17$.

Xem code tham khảo (C++ / Python)

#include <bits/stdc++.h>
using namespace std;

const long long MOD = 1000000007;
long long a[300005];
int L[300005], R[300005];

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];
    stack<int> st;
    for(int i = 0; i < n; i++){                      // nhỏ hơn hẳn bên trái
        while(!st.empty() && a[st.top()] >= a[i]) st.pop();
        L[i] = st.empty() ? -1 : st.top();
        st.push(i);
    }
    while(!st.empty()) st.pop();
    for(int i = n - 1; i >= 0; i--){                 // nhỏ hơn hoặc bằng bên phải
        while(!st.empty() && a[st.top()] > a[i]) st.pop();
        R[i] = st.empty() ? n : st.top();
        st.push(i);
    }
    long long ans = 0;
    for(int i = 0; i < n; i++){
        long long cnt = 1LL * (i - L[i]) * (R[i] - i) % MOD;   // số đoạn nhận a[i] làm min
        ans = (ans + a[i] % MOD * cnt) % MOD;
    }
    cout << ans;
    return 0;
}

import sys

MOD = 10**9 + 7
data = sys.stdin.buffer.read().split()
n = int(data[0])
a = list(map(int, data[1:n + 1]))
L, R, st = [-1] * n, [n] * n, []
for i in range(n):                       # nhỏ hơn hẳn bên trái
    while st and a[st[-1]] >= a[i]:
        st.pop()
    L[i] = st[-1] if st else -1
    st.append(i)
st = []
for i in range(n - 1, -1, -1):           # nhỏ hơn hoặc bằng bên phải
    while st and a[st[-1]] > a[i]:
        st.pop()
    R[i] = st[-1] if st else n
    st.append(i)
print(sum(a[i] * (i - L[i]) * (R[i] - i) for i in range(n)) % MOD)

Bài 7Đoạn ổn định dài nhấtKhá

Một cảm biến ghi lại $n$ số đo $a_1, \ldots, a_n$ ($n \le 5 \cdot 10^5$, $|a_i| \le 10^9$). Một đoạn liên tiếp gọi là ổn định nếu số lớn nhất trừ số nhỏ nhất trong đoạn không vượt quá $K$ ($0 \le K \le 2 \cdot 10^9$). Tìm độ dài đoạn ổn định dài nhất.

Input

8 2
1 3 6 4 5 7 2 2

Output

3

📝 Nộp bài, chấm tự động trên ClueOJ ↗

💡 Gợi ý

Kết hợp hai con trỏ với hai deque. Đoạn ổn định thì mọi đoạn con của nó cũng ổn định, nên khi đầu phải $r$ tăng, đầu trái tốt nhất $l$ chỉ tiến lên. Với mỗi $r$: đẩy $r$ vào deque max và deque min; trong khi $\max - \min > K$ thì tăng $l$ và bỏ đầu deque nào có chỉ số $< l$. Cập nhật đáp án $r - l + 1$. Hai đầu đoạn cùng tiến nên deque vẫn dùng được dù độ dài đoạn thay đổi. Trong ví dụ, đoạn 6 4 5 có $6 - 4 = 2$, dài 3.

Xem code tham khảo (C++ / Python)

#include <bits/stdc++.h>
using namespace std;

long long a[500005];

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n; long long K;
    cin >> n >> K;
    for(int i = 0; i < n; i++) cin >> a[i];
    deque<int> mx, mn;
    int l = 0, best = 0;
    for(int r = 0; r < n; r++){
        while(!mx.empty() && a[mx.back()] <= a[r]) mx.pop_back();
        while(!mn.empty() && a[mn.back()] >= a[r]) mn.pop_back();
        mx.push_back(r); mn.push_back(r);
        while(a[mx.front()] - a[mn.front()] > K){    // đoạn [l, r] chưa ổn định
            l++;
            if(mx.front() < l) mx.pop_front();
            if(mn.front() < l) mn.pop_front();
        }
        best = max(best, r - l + 1);
    }
    cout << best;
    return 0;
}

import sys
from collections import deque

data = sys.stdin.buffer.read().split()
n, K = int(data[0]), int(data[1])
a = list(map(int, data[2:2 + n]))
mx, mn = deque(), deque()
l = best = 0
for r in range(n):
    x = a[r]
    while mx and a[mx[-1]] <= x:
        mx.pop()
    while mn and a[mn[-1]] >= x:
        mn.pop()
    mx.append(r); mn.append(r)
    while a[mx[0]] - a[mn[0]] > K:       # đoạn [l, r] chưa ổn định
        l += 1
        if mx[0] < l:
            mx.popleft()
        if mn[0] < l:
            mn.popleft()
    best = max(best, r - l + 1)
print(best)

Bài 8Mảnh đất trống lớn nhấtKhá

Bản đồ một khu đất là bảng $m \times n$ ô ($m \cdot n \le 10^6$), ô 1 là đất trống, ô 0 là đã có công trình. Tìm hình chữ nhật (cạnh song song với lưới) lớn nhất chỉ gồm các ô 1, in ra số ô của nó. Mỗi dòng của bảng cho dưới dạng một xâu $n$ ký tự.

Input

4 5
10100
10111
11111
10010

Output

6

📝 Nộp bài, chấm tự động trên ClueOJ ↗

💡 Gợi ý

Lần lượt coi mỗi dòng $r$ là đáy của hình chữ nhật. Gọi $h_c$ = số ô 1 liên tiếp kéo thẳng lên từ ô $(r, c)$: nếu ô là 1 thì $h_c$ tăng 1, nếu là 0 thì $h_c = 0$. Khi đó mỗi dòng là một biểu đồ cột, và ta giải bài hình chữ nhật lớn nhất (phần 3) cho từng dòng. Tổng $O(m \cdot n)$. Trong ví dụ, ở dòng thứ ba chiều cao là 3 1 3 2 2, hình chữ nhật cao 2 phủ ba cột cuối được 6 ô.

Xem code tham khảo (C++ / Python)

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int m, n;
    cin >> m >> n;
    vector<int> h(n + 1, 0);              // h[n] = 0 là cột ảo ép mọi cột ra
    vector<int> st;
    long long best = 0;
    for(int r = 0; r < m; r++){
        string row;
        cin >> row;
        for(int c = 0; c < n; c++) h[c] = (row[c] == '1') ? h[c] + 1 : 0;
        st.clear();
        for(int i = 0; i <= n; i++){       // hình chữ nhật lớn nhất, một lần duyệt
            while(!st.empty() && h[st.back()] >= h[i]){
                long long hh = h[st.back()];
                st.pop_back();
                int left = st.empty() ? -1 : st.back();
                best = max(best, hh * (i - left - 1));
            }
            st.push_back(i);
        }
    }
    cout << best;
    return 0;
}

import sys

data = sys.stdin.read().split()
m, n = int(data[0]), int(data[1])
h = [0] * (n + 1)                        # h[n] = 0 là cột ảo ép mọi cột ra
best = 0
for r in range(m):
    row = data[2 + r]
    h = [h[c] + 1 if row[c] == '1' else 0 for c in range(n)] + [0]
    st = []
    for i in range(n + 1):               # hình chữ nhật lớn nhất, một lần duyệt
        while st and h[st[-1]] >= h[i]:
            hh = h[st.pop()]
            left = st[-1] if st else -1
            if hh * (i - left - 1) > best:
                best = hh * (i - left - 1)
        st.append(i)
print(best)

Bài tiếp theo · Bài 26

Toán modulo và tổ hợp

Lũy thừa nhanh, nghịch đảo modulo, tính $C(n, k) \bmod p$ với $n$ tới $10^6$: bộ công cụ số học không thể thiếu cho mọi bài đếm có đáp án “chia lấy dư cho $10^9 + 7$”.

Học bài 26 →

← Bài 24: Chia để trịXem cả series Thuật toán nâng cao

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇

Bản quyền thuộc về Thầy Nguyễn Việt Nam Sơn. Bài viết, lời giải, hình minh hoạ và mã nguồn trên trang là công sức biên soạn của thầy qua nhiều năm giảng dạy. Vui lòng không sao chép, đăng lại hay sử dụng dưới mọi hình thức khi chưa được sự đồng ý của tác giả. Nếu thấy hữu ích, hãy chia sẻ bằng đường link bài gốc nhé. Cảm ơn bạn!