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

Mức độ: Nâng cao

Với mỗi ngày trong 10⁵ ngày, hỏi phải đợi bao nhiêu ngày mới có ngày nóng hơn. Với mỗi ngày tìm tiếp sang phải thì có thể mất tới n bước, cả bài 10¹⁰ bước. Ngăn xếp đơn điệu trả lời cho cả n ngày chỉ trong khoảng 2n bước. Bài này dùng ngăn xếp và hàng đợi hai đầu (deque), các bạn xem lại nếu chưa quen.

Ngăn xếp đơn điệu: số lớn hơn tiếp theo

Bài toán: với mỗi vị trí i, tìm vị trí j đầu tiên bên phải có a_j lớn hơn a_i.

Đi từ trái sang phải, giữ trong ngăn xếp các vị trí chưa tìm được số lớn hơn. Khi gặp a_j:

• trong khi đỉnh ngăn xếp là vị trí i có a_i nhỏ hơn a_j: đáp án của i là j, lấy i ra;
• đưa j vào ngăn xếp.

Các giá trị trong ngăn xếp luôn giảm dần từ đáy lên đỉnh (vì số nào nhỏ hơn số mới đều đã bị lấy ra), nên gọi là ngăn xếp đơn điệu. Nhờ thứ tự này, khi đỉnh không nhỏ hơn a_j thì các vị trí bên dưới (còn lớn hơn) cũng không nhỏ hơn, dừng được ngay.

Dãy 2 7 3 1 5 8:

j	aj	Lấy ra (tìm được đáp án là j)	Ngăn xếp sau (giá trị)
1	2		2
2	7	vị trí 1 (số 2)	7
3	3		7 3
4	1		7 3 1
5	5	vị trí 4 (số 1), vị trí 3 (số 3)	7 5
6	8	vị trí 5 (số 5), vị trí 2 (số 7)	8

Còn lại vị trí 6 không có số lớn hơn. Số lớn hơn tiếp theo của từng số: 7 8 5 5 8 -1.

Vì sao chỉ khoảng 2n bước? Mỗi vị trí được đưa vào ngăn xếp đúng một lần và lấy ra nhiều nhất một lần. Vòng while bên trong có lúc chạy nhiều lần, nhưng tổng số lần chạy trên cả bài không quá n.

Python

import sys
du_lieu = sys.stdin.read().split()
n = int(du_lieu[0])
a = list(map(int, du_lieu[1:1 + n]))
ket_qua = [-1] * n
ngan_xep = []                       # các vị trí chưa tìm được số lớn hơn
for j in range(n):
    while ngan_xep and a[ngan_xep[-1]] < a[j]:
        ket_qua[ngan_xep.pop()] = a[j]
    ngan_xep.append(j)
print(*ket_qua)

C++

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long> a(n), ketQua(n, -1);
    for (auto &x : a) cin >> x;
    vector<int> nganXep;             // các vị trí chưa tìm được số lớn hơn
    for (int j = 0; j < n; j++) {
        while (!nganXep.empty() && a[nganXep.back()] < a[j]) {
            ketQua[nganXep.back()] = a[j];
            nganXep.pop_back();
        }
        nganXep.push_back(j);
    }
    for (int i = 0; i < n; i++) cout << ketQua[i] << (i + 1 < n ? ' ' : '\n');
    return 0;
}

Đổi dấu so sánh và chiều đi là được các biến thể: số nhỏ hơn tiếp theo, số lớn hơn gần nhất bên trái, …

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

Biểu đồ có n cột rộng 1, cao h₁, …, h_n. Tìm hình chữ nhật lớn nhất nằm trong biểu đồ. Hình chữ nhật tốt nhất luôn có chiều cao bằng một cột nào đó (nếu không thì tăng chiều cao lên được). Với cột i làm chiều cao, hình kéo dài sang trái và phải đến khi gặp cột thấp hơn.

Vậy cần, với mỗi i, vị trí cột thấp hơn gần nhất bên trái L_i và bên phải R_i; hình chữ nhật dùng cột i có diện tích h_i × (R_i - L_i - 1). Cả hai dãy L, R tính bằng ngăn xếp đơn điệu.

Cột 2 1 5 6 2 3: cột cao 5 (vị trí 3) kéo được tới cột 4, rộng 2, diện tích 10. Cột cao 2 (vị trí 5) kéo từ vị trí 3 đến 6, rộng 4, diện tích 8. Lớn nhất là 10.

Hàng đợi đơn điệu: lớn nhất của mọi cửa sổ

Tìm giá trị lớn nhất của mọi đoạn k số liên tiếp. Dùng deque chứa các vị trí trong cửa sổ, giữ giá trị giảm dần từ đầu đến cuối:

• số mới vào: bỏ ở cuối deque mọi vị trí có giá trị không lớn hơn số mới (chúng đứng trước, nhỏ hơn, nên không bao giờ còn là lớn nhất nữa), rồi thêm số mới vào cuối;
• vị trí ở đầu deque đã ra khỏi cửa sổ thì bỏ đi;
• giá trị lớn nhất của cửa sổ là phần tử ở đầu deque.

Dãy 1 3 -1 -3 5 3 6, k = 3:

Vào	Deque (giá trị)	Cửa sổ	Lớn nhất
1	1
3	3
-1	3 -1	1 3 -1	3
-3	3 -1 -3	3 -1 -3	3
5	5	-1 -3 5	5
3	5 3	-3 5 3	5
6	6	5 3 6	6

Python

import sys
from collections import deque
du_lieu = sys.stdin.read().split()
n, k = int(du_lieu[0]), int(du_lieu[1])
a = list(map(int, du_lieu[2:2 + n]))
hang_doi = deque()                  # vị trí, giá trị giảm dần
ket_qua = []
for i in range(n):
    while hang_doi and a[hang_doi[-1]] <= a[i]:
        hang_doi.pop()
    hang_doi.append(i)
    if hang_doi[0] <= i - k:        # đầu deque đã ra khỏi cửa sổ
        hang_doi.popleft()
    if i >= k - 1:
        ket_qua.append(a[hang_doi[0]])
print(*ket_qua)

C++

#include <iostream>
#include <vector>
#include <deque>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<long long> a(n);
    for (auto &x : a) cin >> x;
    deque<int> hangDoi;              // vị trí, giá trị giảm dần
    vector<long long> ketQua;
    for (int i = 0; i < n; i++) {
        while (!hangDoi.empty() && a[hangDoi.back()] <= a[i]) hangDoi.pop_back();
        hangDoi.push_back(i);
        if (hangDoi.front() <= i - k) hangDoi.pop_front();   // đã ra khỏi cửa sổ
        if (i >= k - 1) ketQua.push_back(a[hangDoi.front()]);
    }
    for (size_t i = 0; i < ketQua.size(); i++) cout << ketQua[i] << (i + 1 < ketQua.size() ? ' ' : '\n');
    return 0;
}

Mỗi vị trí vào deque một lần và ra nhiều nhất một lần, cả bài khoảng 2n bước. Hàng đợi đơn điệu dùng được cho cả cửa sổ co giãn: bỏ ở đầu deque mọi vị trí đứng trước trai.

Luyện tập

Gồm 20 bài, chia thành 5 nhóm từ dễ đến khó. Mỗi bài có một dữ liệu kiểm tra: các bạn chạy chương trình của mình với dữ liệu đó rồi so với đáp số.

Nhóm 1. Số lớn hơn, nhỏ hơn gần nhất

Bài 1. Số lớn hơn tiếp theo

Dòng đầu có n (1 ≤ n ≤ 10⁵), dòng thứ hai có n số nguyên (|a_i| ≤ 10⁹). Với mỗi số, in ra số đầu tiên bên phải nó lớn hơn nó, hoặc -1 nếu không có.

Ví dụ:

Nhập	In ra
6 2 7 3 1 5 8	7 8 5 5 8 -1

Kiểm tra: nhập

10
5 5 3 9 -2 0 9 10 1 1

Xem đáp số

9 9 9 10 0 9 10 -1 -1 -1

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 2. Số nhỏ hơn gần nhất bên trái

Dòng đầu có n (1 ≤ n ≤ 10⁵), dòng thứ hai có n số nguyên (|a_i| ≤ 10⁹). Với mỗi vị trí i (đánh số từ 1), in ra vị trí j gần nhất bên trái có a_j nhỏ hơn a_i, hoặc 0 nếu không có.

Ví dụ:

Nhập	In ra
6 4 2 6 5 6 1	0 0 2 2 4 0

Kiểm tra: nhập

10
3 3 8 1 9 9 2 7 4 0

Xem đáp số

0 0 2 0 4 4 4 7 7 0

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 3. Đợi ngày nóng hơn

Dòng đầu có n (1 ≤ n ≤ 10⁵), dòng thứ hai có nhiệt độ n ngày liên tiếp (|t_i| ≤ 100). Với mỗi ngày, in ra số ngày phải đợi đến ngày đầu tiên nóng hơn, hoặc 0 nếu không có ngày nào như vậy.

Ví dụ:

Nhập	In ra
8 23 24 25 21 19 22 26 23	1 1 4 2 1 1 0 0

Kiểm tra: nhập

10
30 28 28 31 27 29 35 30 33 35

Xem đáp số

3 2 1 3 1 1 0 1 1 0

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 4. Chuỗi ngày giá không cao hơn

Giá một cổ phiếu trong n ngày là p₁, …, p_n. Với mỗi ngày i, in ra số ngày liên tiếp kết thúc ở ngày i (tính cả ngày i, đi ngược về trước) mà giá mỗi ngày không cao hơn p_i. Dòng đầu có n (1 ≤ n ≤ 10⁵), dòng thứ hai có n số p_i (1 ≤ p_i ≤ 10⁹).

Ví dụ:

Nhập	In ra
7 100 80 60 70 60 75 85	1 1 1 2 1 4 6

Kiểm tra: nhập

10
5 5 5 3 6 6 1 7 2 7

Xem đáp số

1 2 3 1 5 6 1 8 1 10

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 5. Số lớn hơn tiếp theo trên vòng tròn

n số xếp thành vòng tròn: sau số cuối là số đầu. Dòng đầu có n (1 ≤ n ≤ 10⁵), dòng thứ hai có n số nguyên (|a_i| ≤ 10⁹). Với mỗi số, đi theo chiều vòng tròn, in ra số đầu tiên lớn hơn nó, hoặc -1000000001 nếu không có.

Ví dụ:

Nhập	In ra
5 3 8 4 1 2	8 -1000000001 8 2 3

Kiểm tra: nhập

8
-5 9 9 0 -3 7 9 -1

Xem đáp số

9 -1000000001 -1000000001 7 7 9 -1000000001 9

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 6. Tòa nhà nhìn thấy biển

n tòa nhà xếp thành hàng từ trái sang phải, biển ở bên phải tòa cuối cùng. Một tòa nhìn thấy biển nếu nó cao hơn hẳn mọi tòa bên phải nó. Dòng đầu có n (1 ≤ n ≤ 10⁵), dòng thứ hai có n chiều cao (1 ≤ h_i ≤ 10⁹). In ra vị trí (đánh số từ 1) các tòa nhìn thấy biển, theo thứ tự từ trái sang phải.

Ví dụ:

Nhập	In ra
6 4 2 3 1 3 2	1 5 6

Kiểm tra: nhập

10
7 9 3 9 8 2 5 5 1 4

Xem đáp số

4 5 8 10

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 2. Đóng góp của từng phần tử

Bài 7. Tổng giá trị nhỏ nhất của mọi đoạn

Dòng đầu có n (1 ≤ n ≤ 10⁵), dòng thứ hai có n số nguyên (1 ≤ a_i ≤ 10⁶). Với mỗi đoạn liên tiếp (có n × (n + 1) / 2 đoạn), lấy số nhỏ nhất của đoạn. In ra tổng các số nhỏ nhất đó.

Ví dụ:

Nhập	In ra
4 3 1 2 4	17

Kiểm tra: nhập

10
5 2 8 2 6 1 9 4 4 7

Xem đáp số

121

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 8. Tổng độ chênh của mọi đoạn

Dòng đầu có n (1 ≤ n ≤ 10⁵), dòng thứ hai có n số nguyên (1 ≤ a_i ≤ 10⁶). Độ chênh của một đoạn là số lớn nhất trừ số nhỏ nhất trong đoạn. In ra tổng độ chênh của mọi đoạn liên tiếp.

Ví dụ:

Nhập	In ra
3 1 3 2	5

Kiểm tra: nhập

10
4 9 1 1 7 3 8 2 6 5

Xem đáp số

290

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 9. Mỗi số là lớn nhất của bao nhiêu đoạn

Dòng đầu có n (1 ≤ n ≤ 10⁵), dòng thứ hai có n số nguyên đôi một khác nhau (|a_i| ≤ 10⁹). Với mỗi vị trí i, in ra số đoạn liên tiếp chứa i mà a_i là số lớn nhất của đoạn.

Ví dụ:

Nhập	In ra
4 2 5 1 3	1 6 1 2

Kiểm tra: nhập

8
6 -2 8 3 1 7 0 9

Xem đáp số

2 1 15 2 1 6 1 8

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 10. Cặp người nhìn thấy nhau

n người đứng thành hàng, người thứ i cao h_i. Hai người i và j (i đứng trước j) nhìn thấy nhau nếu mọi người đứng giữa họ đều không cao hơn người thấp hơn trong hai người. Dòng đầu có n (1 ≤ n ≤ 10⁵), dòng thứ hai có n số h_i (1 ≤ h_i ≤ 10⁹). In ra số cặp nhìn thấy nhau.

Ví dụ:

Nhập	In ra
7 2 4 1 2 2 5 1	10

Kiểm tra: nhập

10
3 3 1 3 2 5 2 2 4 3

Xem đáp số

17

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 3. Hình chữ nhật và nước mưa

Bài 11. Hình chữ nhật lớn nhất trong biểu đồ cột

Biểu đồ có n cột rộng 1, cột thứ i cao h_i. Dòng đầu có n (1 ≤ n ≤ 10⁵), dòng thứ hai có n số h_i (0 ≤ h_i ≤ 10⁹). In ra diện tích hình chữ nhật lớn nhất nằm trong biểu đồ (cạnh song song với trục).

Ví dụ:

Nhập	In ra
6 2 1 5 6 2 3	10

Kiểm tra: nhập

10
6 2 5 4 5 1 6 6 6 2

Xem đáp số

18

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 12. Mảnh đất trống lớn nhất

Bản đồ là bảng m hàng, n cột gồm 0 (đất trống) và 1 (có nhà). Dòng đầu có m, n (1 ≤ m, n ≤ 1000), m dòng sau mỗi dòng là một xâu n ký tự. In ra diện tích hình chữ nhật lớn nhất chỉ gồm ô đất trống.

Ví dụ:

Nhập	In ra
4 5 10100 00000 00010 01000	6

Kiểm tra: nhập

6 7
0010000
0000100
1000000
0001000
0000001
0100000

Xem đáp số

8

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 13. Nước mưa đọng lại

Địa hình gồm n cột rộng 1, cột thứ i cao h_i. Sau cơn mưa, nước đọng ở các chỗ trũng. Dòng đầu có n (1 ≤ n ≤ 10⁵), dòng thứ hai có n số h_i (0 ≤ h_i ≤ 10⁹). In ra tổng lượng nước đọng (số ô vuông đơn vị).

Ví dụ:

Nhập	In ra
12 0 1 0 2 1 0 1 3 2 1 2 1	6

Kiểm tra: nhập

10
4 2 0 3 2 5 1 1 6 0

Xem đáp số

17

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 4. Hàng đợi đơn điệu

Bài 14. Lớn nhất của mọi cửa sổ

Dòng đầu có n, k (1 ≤ k ≤ n ≤ 10⁶), dòng thứ hai có n số nguyên (|a_i| ≤ 10⁹). In ra số lớn nhất của từng đoạn k số liên tiếp, từ trái sang phải.

Ví dụ:

Nhập	In ra
7 3 1 3 -1 -3 5 3 6	3 3 5 5 6

Kiểm tra: nhập

12 4
2 8 -5 8 3 1 0 -7 9 9 -2 4

Xem đáp số

8 8 8 8 3 9 9 9 9

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 15. Đoạn dài nhất có độ chênh không quá D

Dòng đầu có n, D (1 ≤ n ≤ 10⁵, 0 ≤ D ≤ 10⁹), dòng thứ hai có n số nguyên (|a_i| ≤ 10⁹). In ra độ dài lớn nhất của một đoạn liên tiếp mà (số lớn nhất) - (số nhỏ nhất) trong đoạn không quá D.

Ví dụ:

Nhập	In ra
7 3 4 8 6 5 9 7 1	3

Kiểm tra: nhập

12 5
10 12 8 14 13 9 15 20 18 17 22 3

Xem đáp số

4

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 16. Đếm đoạn có độ chênh không quá D

Dòng đầu có n, D (1 ≤ n ≤ 10⁵, 0 ≤ D ≤ 10⁹), dòng thứ hai có n số nguyên (|a_i| ≤ 10⁹). In ra số đoạn liên tiếp mà (số lớn nhất) - (số nhỏ nhất) trong đoạn không quá D.

Ví dụ:

Nhập	In ra
4 1 1 2 3 2	8

Kiểm tra: nhập

12 4
10 12 8 14 13 9 15 20 18 17 22 3

Xem đáp số

20

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 17. Nhảy qua các bậc

Có n bậc thang, bậc thứ i có điểm thưởng a_i (có thể âm). Bắt đầu ở bậc 1, mỗi lần nhảy lên phía trước từ 1 đến k bậc, phải dừng ở bậc n. Điểm là tổng điểm các bậc đã dừng chân (gồm bậc 1 và bậc n). Dòng đầu có n, k (1 ≤ k ≤ n ≤ 10⁵), dòng thứ hai có n số a_i (|a_i| ≤ 10⁴). In ra điểm lớn nhất.

Ví dụ:

Nhập	In ra
6 2 1 -1 -2 4 -7 3	7

Kiểm tra: nhập

10 3
5 -10 -3 2 -8 -8 -1 6 -20 4

Xem đáp số

16

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 18. Đoạn có độ dài từ L đến R tổng lớn nhất

Dòng đầu có n, L, R (1 ≤ L ≤ R ≤ n ≤ 10⁵), dòng thứ hai có n số nguyên (|a_i| ≤ 10⁹). In ra tổng lớn nhất của một đoạn liên tiếp có độ dài từ L đến R.

Ví dụ:

Nhập	In ra
6 2 3 -1 4 -2 3 5 -6	8

Kiểm tra: nhập

10 3 5
2 -8 6 -1 3 -4 7 -2 1 5

Xem đáp số

11

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 5. Ngăn xếp với xâu

Bài 19. Xóa k chữ số để được số nhỏ nhất

Nhập xâu chữ số s (1 ≤ |s| ≤ 10⁵) và số k (0 ≤ k ≤ |s|) trên hai dòng. Xóa đú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 ra số đó, bỏ các chữ số 0 ở đầu; nếu không còn chữ số nào hoặc chỉ còn chữ số 0 thì in ra 0.

Ví dụ:

Nhập	In ra
1432219 3	1219

Kiểm tra: nhập

10200
1

Xem đáp số

200

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 20. Dãy ngoặc đúng dài nhất

Nhập một xâu gồm các ký tự ( và ) (1 ≤ độ dài ≤ 10⁵). In ra độ dài lớn nhất của một đoạn liên tiếp là dãy ngoặc đúng.

Ví dụ: nhập (()())(() thì in ra 6.

Kiểm tra: nhập )()(()))()()((().

Xem đáp số

6

Hướng dẫn giải chi tiết: liên hệ tác giả.

Lời giải chi tiết các bài luyện tập

Đáp số của từng bài ở ngay dưới đề để các bạn tự kiểm tra. Lời giải chi tiết (phân tích, chạy tay, chương trình Python và C++, lưu ý khi làm bài) có trong bộ tài liệu có phí của chuyên đề.

Thầy cô và các bạn muốn mua bộ tài liệu vui lòng liên hệ tác giả qua Zalo 0972465159 hoặc Facebook.