Dùng cửa sổ trượt để xử lý đoạn liên tiếp

Lan ghi lại số chai nước bán được trong bảy ngày: 4, 1, 3, 2, 6, 1, 5. Bạn ấy muốn tìm ba ngày liên tiếp có tổng lớn nhất. Tính lại từng đoạn được, nhưng một năm có nhiều đoạn hơn. Có cách nào giữ lại phần tính toán đã làm?

Một cửa sổ giữ trạng thái của một đoạn liên tiếp

Cửa sổ trượt (sliding window) là đoạn liên tiếp được mô tả bởi hai đầu. Khi một đầu di chuyển, ta cập nhật trạng thái thay vì tính lại toàn bộ đoạn. Trạng thái có thể là tổng, số phần tử lẻ hoặc bảng tần suất.

Đánh số từ 0, đoạn [l, r] gồm cả hai đầu và có r - l + 1 phần tử. Đoạn rỗng có thể biểu diễn bằng l = r + 1. Hai hình dưới đây giữ nguyên dữ liệu, chỉ thay vị trí cửa sổ.

Tổng trước là tổng của 4, 1, 3. Tổng sau bỏ 4 và thêm 2. Hai phần tử 1 và 3 vẫn nằm trong cửa sổ nên không cần cộng lại.

a = [4, 1, 3, 2, 6, 1, 5]
current = sum(a[:3])
print("Trước:", current)
current = current - a[0] + a[3]
print("Sau:", current)

Trước: 8
Sau: 6

Chạy khối trên cho thấy phép cập nhật khớp với tổng của ba số 1, 3, 2. Nếu đoạn không liên tiếp, việc bỏ trái và thêm phải không biểu diễn được mọi lựa chọn. Khi ấy cần xét kỹ thuật khác.

Độ dài cố định cho phép bỏ một phần tử rồi thêm một phần tử

Với 1 <= k <= n, ta tìm tổng lớn nhất trong mọi đoạn dài đúng k. Trước tiên tính tổng k phần tử đầu. Mỗi lần dịch, phần tử a[r-k] rời cửa sổ và a[r] đi vào.

7 3
4 1 3 2 6 1 5

n, k = map(int, input().split())
a = list(map(int, input().split()))
current = sum(a[:k])
best = current
for r in range(k, n):
    current += a[r] - a[r-k]
    best = max(best, current)
print(best)

12

Khối chạy xét các đoạn theo thứ tự đầu trái từ 0 đến n-k. Ban đầu current đúng cho đoạn đầu. Sau mỗi lần dịch, chỉ một phần tử ra và một phần tử vào, nên tổng vẫn đúng. Vì mọi đoạn dài k được xét đúng một lần, best là tổng lớn nhất.

Khởi tạo best bằng tổng đầu tiên thay vì 0. Nếu tất cả số đều âm, 0 có thể không phải tổng của đoạn nào. Ví dụ sau chứa ba số âm và cửa sổ dài hai.

Nếu k = n, chỉ có một cửa sổ và vòng dịch không chạy, nên vẫn phải ghi nhận tổng ban đầu. Nếu k = 1, mỗi cửa sổ chỉ có một phần tử và phép cập nhật vẫn hoạt động.

a = [-8, -3, -5]
k = 2
current = sum(a[:k])
best = current
for r in range(k, len(a)):
    current += a[r] - a[r-k]
    best = max(best, current)
print(best)

-8

Tính tổng đầu mất k phép cộng; các lần dịch mất n-k bước. Với n = 100000, công việc tỉ lệ khoảng 100000 bước, thay vì khoảng n*k khi cộng lại từng đoạn. Thuật toán cần O(n) thời gian và O(1) bộ nhớ phụ ngoài danh sách đầu vào.

Co cửa sổ khi tổng vượt giới hạn trên

Bây giờ mỗi số là thời gian không âm. Tìm đoạn dài nhất có tổng không vượt S. Ta thêm a[r], rồi bỏ dần bên trái khi tổng quá lớn. Sau khi co, cửa sổ là hợp lệ; nếu một phần tử riêng đã lớn hơn S, cửa sổ có thể rỗng.

Ở hàng đầu, tổng là 6 nên bỏ số 2 ở bên trái. Đoạn còn lại có tổng 4. Mở rộng tiếp bằng số 0 không làm tổng thay đổi.

5 5
2 1 3 0 2

n, limit = map(int, input().split())
a = list(map(int, input().split()))
left = 0
total = 0
best = 0
for right in range(n):
    total += a[right]
    while total > limit:
        total -= a[left]
        left += 1
    best = max(best, right - left + 1)
print(best)

3

Vì các số không âm, bỏ bên trái không làm tổng tăng. Mỗi đầu trái bị bỏ tại thời điểm tổng vượt giới hạn. Mọi đoạn kết thúc muộn hơn và bắt đầu tại đầu trái đó cũng có tổng ít nhất như vậy. Do đó không đoạn hợp lệ nào cần đầu trái đã bỏ.

Khi đã co xong, left là đầu trái sớm nhất còn có thể hợp lệ với right. Cửa sổ hiện tại dài nhất trong các đoạn hợp lệ kết thúc tại right. Lấy độ dài lớn nhất trên mọi right cho đáp án toàn dãy.

Khởi tạo best bằng 0 để biểu diễn trường hợp không chọn được phần tử nào. Số 0 trong dữ liệu vẫn có thể tạo cửa sổ hợp lệ khi giới hạn bằng 0. Điều kiện không âm cần được kiểm tra trong đề trước khi áp dụng cách co này.

Tuy có vòng while bên trong, left chỉ tăng từ 0 đến nhiều nhất n. Mỗi phần tử được thêm một lần và bỏ nhiều nhất một lần. Vì vậy thời gian là O(n), bộ nhớ phụ O(1). Với n = 100000, số lần di chuyển của hai đầu không vượt khoảng 200000.

Một cửa sổ hợp lệ giúp đếm nhiều đoạn cùng lúc

Giả sử cửa sổ [left, right] có tổng không vượt S. Mọi đoạn bắt đầu tại left, left+1, ..., right và kết thúc tại right cũng hợp lệ. Bỏ thêm số không âm ở bên trái không thể làm tổng tăng. Vì thế ta cộng right - left + 1, không chỉ cộng 1.

Ví dụ với dãy 2, 1, 3 và giới hạn 4, ở đầu phải cuối cùng có hai đoạn hợp lệ: [1, 3] và [3]. Khối sau in số đoạn mới ở từng bước cùng tổng cuối cùng.

a = [2, 1, 3]
limit = 4
left = total = answer = 0
for right, value in enumerate(a):
    total += value
    while total > limit:
        total -= a[left]
        left += 1
    added = right - left + 1
    answer += added
    print("Đầu phải", right, "thêm", added)
print("Tổng số đoạn:", answer)

Đầu phải 0 thêm 1
Đầu phải 1 thêm 2
Đầu phải 2 thêm 2
Tổng số đoạn: 5

Mỗi đoạn có đúng một đầu phải, nên không bị đếm hai lần. Các đầu trái trước left không hợp lệ theo lập luận ở mục trước. Mỗi lần thêm và bỏ vẫn chỉ xảy ra tối đa một lần cho mỗi phần tử, nên thời gian là O(n).

Xét dãy 2, 1, 3, 0 với giới hạn 4. Mỗi dòng dưới đây cho biết cửa sổ sau khi đã co. Cột thêm là số đoạn hợp lệ mới kết thúc tại đầu phải đó.

Tại right = 2, tổng tạm thời là 6. Bỏ 2 ở đầu trái đưa tổng về 4, nên hai đầu trái còn lại là 1 và 2. Khi thêm số 0 tại right = 3, đầu trái giữ nguyên và có ba đoạn mới.

Nếu tổng trong bảng khác tổng của các phần tử giữa hai đầu, hãy kiểm tra thứ tự cập nhật. Với bảng tần suất, tổng các tần suất phải bằng độ dài cửa sổ và không còn khóa có tần suất 0.

Số đoạn có thể lớn: với 100000 số 0 và giới hạn 0, tất cả 100000 * 100001 // 2 đoạn đều hợp lệ. Python giữ được số nguyên lớn này. Ở ngôn ngữ có kiểu số nguyên giới hạn, cần chọn kiểu đủ rộng.

n = 100000
print(n * (n + 1) // 2)

5000050000

Đoạn ngắn nhất đạt ngưỡng được cập nhật trước khi co

Cho dãy không âm và target > 0, tìm đoạn không rỗng ngắn nhất có tổng ít nhất target. Khi tổng đã đủ, cửa sổ hiện tại là một ứng viên. Ghi nhận độ dài trước khi bỏ bên trái; sau đó tiếp tục co để tìm ứng viên ngắn hơn.

6 7
2 3 1 2 4 3

n, target = map(int, input().split())
a = list(map(int, input().split()))
left = total = 0
best = n + 1
for right in range(n):
    total += a[right]
    while total >= target:
        best = min(best, right - left + 1)
        total -= a[left]
        left += 1
print(-1 if best == n + 1 else best)

2

Đoạn cuối gồm 4 và 3 đạt ngưỡng với độ dài hai. Không phần tử nào đạt ngưỡng một mình, nên không có đáp án độ dài một. Nếu không có đoạn đủ tổng, best không đổi và chương trình in -1.

Giá trị n + 1 báo chưa tìm thấy vì mọi đoạn không rỗng đều có độ dài từ 1 đến n. Vì thế nó không nhầm với một đáp án thực sự.

Vì sao có thể bỏ một đầu trái sau khi đã ghi nhận cửa sổ? Với cùng đầu trái đó, đoạn kết thúc muộn hơn chỉ dài hơn. Nó không thể cải thiện đáp án vừa ghi. Mọi ứng viên có thể tốt hơn sẽ được xét khi co tiếp hoặc mở sang phải.

Với target > 0, tổng cửa sổ rỗng là 0 và vòng co dừng. Nếu cho phép target <= 0, cần định nghĩa rõ đoạn rỗng có được tính hay không và xử lý riêng. Hai đầu vẫn di chuyển tối đa n lần, nên thời gian O(n) và bộ nhớ phụ O(1).

Đếm phần tử không mong muốn bằng cùng cách co

Không phải trạng thái nào cũng là tổng. Cần tìm đoạn dài nhất có nhiều nhất k số lẻ. Mỗi lần thêm số lẻ, tăng bộ đếm; mỗi lần bỏ số lẻ, giảm bộ đếm. Số lẻ là phần tử được đánh dấu trong bài toán này.

a = [2, 3, 4, 7, 6, 8]
k = 1
left = odd = best = 0
for right, value in enumerate(a):
    odd += value % 2
    while odd > k:
        odd -= a[left] % 2
        left += 1
    best = max(best, right - left + 1)
print(best)

4

Đoạn [4, 7, 6, 8] có một số lẻ. Khi bỏ một phần tử, số phần tử lẻ không tăng. Khi thêm phần tử, số này không giảm. Lập luận loại các đầu trái đã bỏ giống bài giới hạn tổng không âm.

Khi k = 0, cửa sổ chỉ giữ các số chẵn. Nếu mọi số đều lẻ, mỗi lần co có thể để lại cửa sổ rỗng và đáp án là 0. Đây là một biên cần kiểm tra, không phải lỗi chỉ số.

Bảng tần suất giữ số giá trị phân biệt trong cửa sổ

Một cửa hàng muốn chọn đoạn dài nhất gồm không quá hai loại sản phẩm. Đếm số phần tử không đủ: hai sản phẩm cùng loại chỉ tính là một loại. Ta lưu số lần xuất hiện của từng loại trong một từ điển.

Khi số loại vượt giới hạn, bỏ dần bên trái. Một loại chỉ biến mất khỏi cửa sổ khi số lần của nó giảm về 0. Xóa khóa tại thời điểm đó để len(freq) bằng đúng số loại đang hiện diện.

a = [1, 2, 1, 3, 3, 2, 2]
k = 2
freq = {}
left = best = 0
for right, value in enumerate(a):
    freq[value] = freq.get(value, 0) + 1
    while len(freq) > k:
        old = a[left]
        freq[old] -= 1
        if freq[old] == 0:
            del freq[old]
        left += 1
    best = max(best, right - left + 1)
print(best)

4

Đoạn [3, 3, 2, 2] gồm hai loại. Bỏ phần tử không làm tăng số loại, còn thêm phần tử không làm giảm số loại. Vì vậy đầu trái đã bị loại không thể tạo đoạn hợp lệ dài hơn khi đầu phải tiến tiếp.

Mỗi phần tử vào một lần và ra nhiều nhất một lần. Các thao tác từ điển trung bình O(1), nên thời gian trung bình O(n). Bộ nhớ là O(min(n, k + 1)) trong quá trình mở rồi co. Với k = 0, mỗi phần tử vừa thêm đều được bỏ và đáp án bằng 0.

Số âm có thể làm một đầu trái bị bỏ quá sớm

Quy tắc co tổng trên không áp dụng nguyên xi cho dãy có số âm. Xét dãy 5, -10, 1 và giới hạn 1. Khi gặp số 5, cách co tổng bỏ nó vì 5 lớn hơn 1. Nhưng cả ba số có tổng 5 - 10 + 1 = -4, không vượt 1: đoạn hợp lệ dài nhất lại bắt đầu đúng ở đầu trái vừa bị bỏ. Số âm phía sau kéo tổng xuống, nên lập luận "tổng đã vượt thì mở rộng thêm cũng vượt" không còn đúng.

Khối sau so sánh cách co không phù hợp với duyệt mọi đoạn. Kết quả máy chạy cho thấy cách đầu bỏ lỡ một đoạn dài hơn.

a = [5, -10, 1]
limit = 1
left = total = wrong = 0
for right, value in enumerate(a):
    total += value
    while left <= right and total > limit:
        total -= a[left]
        left += 1
    wrong = max(wrong, right - left + 1)
brute = 0
for l in range(len(a)):
    s = 0
    for r in range(l, len(a)):
        s += a[r]
        if s <= limit:
            brute = max(brute, r-l+1)
print("Co cửa sổ:", wrong)
print("Duyệt mọi đoạn:", brute)

Co cửa sổ: 2
Duyệt mọi đoạn: 3

Phản ví dụ chỉ bác bỏ quy tắc co tổng vừa dùng. Cửa sổ độ dài cố định vẫn cập nhật tổng được với số âm, vì nó không dựa vào tính không âm. Với tổng bằng một giá trị cho trước và số âm, tổng tiền tố kết hợp từ điển là một hướng khác; xem Bài 12 và Bài 16.

Chọn trạng thái và chứng minh trước khi lập trình

Đoạn dài nhất dưới giới hạn được cập nhật sau khi co về hợp lệ. Đoạn ngắn nhất đạt ngưỡng được cập nhật trong lúc còn hợp lệ, trước mỗi lần bỏ trái. Hai hướng tối ưu khác nhau nên không đổi thứ tự một cách máy móc.

Thử dữ liệu nhỏ bằng cách duyệt mọi đoạn. Với n nhỏ, cách O(n²) dễ đối chiếu đáp án của cách O(n). Thử cửa sổ rỗng, một phần tử, các số bằng 0 và trường hợp không có đoạn thỏa mãn.

a = [0, 2, 0, 1]
limit = 2
left = total = fast = 0
for right, x in enumerate(a):
    total += x
    while total > limit:
        total -= a[left]
        left += 1
    fast += right-left+1
slow = 0
for l in range(len(a)):
    for r in range(l, len(a)):
        slow += sum(a[l:r+1]) <= limit
print("Cửa sổ:", fast)
print("Duyệt:", slow)

Cửa sổ: 8
Duyệt: 8

Hai cách cùng giải một yêu cầu, nhưng cách duyệt lại dùng nhiều phép tính hơn. Trên dữ liệu lớn, không nên dùng ví dụ đối chiếu này làm lời giải chính.

Lỗi thường gặp

Tóm tắt

Cửa sổ cố định giữ đúng độ dài và cập nhật phần vào, phần ra. Cửa sổ thay đổi cần trạng thái chính xác và lập luận cho mỗi đầu trái bị bỏ. Với số không âm, tổng và số phần tử vi phạm cho phép co theo những quy tắc đã xét. Bảng tần suất xử lý số loại phân biệt.

Kiểm tra nhanh

Đọc thêm

• Tài liệu Python về từ điển.
• Tài liệu Python về độ phức tạp của số nguyên.