Sliding Window Maximum

Q: Độ phức tạp thời gian của bài toán tìm giá trị lớn nhất trong cửa sổ trượt là bao nhiêu?

Lời giải bằng deque đơn điệu chạy trong thời gian O(n) , vì mỗi chỉ số được thêm vào một lần và bị loại ra nhiều nhất một lần. Deque chứa tối đa k chỉ số, nên ngoài phần kết quả, cần thêm O(k) bộ nhớ.

KhóCửa sổ trượt Ngăn xếp đơn điệu Hàng đợi

+10

Bạn được cung cấp một mảng số nguyên nums và kích thước cửa sổ k. Một cửa sổ gồm k giá trị liên tiếp bắt đầu từ đầu bên trái và dịch sang phải từng vị trí một cho đến khi cạnh phải nằm ở giá trị cuối cùng. Hãy trả về giá trị lớn nhất trong cửa sổ ở mỗi vị trí, từ trái sang phải: n-k+1 giá trị đối với một mảng có độ dài n.

Hàm

maxSlidingWindow(nums: integer-array, k: integer) → integer-array

numsinteger-array: mảng mà cửa sổ trượt qua
kinteger: số lượng giá trị trong mỗi cửa sổ
Trả vềinteger-array: giá trị lớn nhất của mỗi cửa sổ, từ cửa sổ ngoài cùng bên trái đến cửa sổ ngoài cùng bên phải

Ràng buộc

1 ≤ k ≤ nums.length ≤ 2 × 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
Kết quả chứa nums.length-k+1 giá trị, mỗi cửa sổ có một giá trị, theo thứ tự từ trái sang phải.

Ví dụ

Đầu vào: nums = [4, 2, 12, 3, 8, 5, 1]k = 3
Đầu ra: [12, 12, 12, 8, 8]
Giải thích: 12 nằm trong ba cửa sổ đầu tiên, nên mỗi cửa sổ đều trả về 12. Sau khi 12 trượt ra ngoài, [3, 8, 5] và [8, 5, 1] đều có giá trị lớn nhất là 8.

Đầu vào: nums = [-3, -1, -7, -2]k = 2
Đầu ra: [-1, -1, -2]
Giải thích: Các khoảng là [-3, -1], [-1, -7] và [-7, -2]. Số lớn hơn trong hai số âm là số gần 0 hơn, nên ta có -1, -1 và -2.

Đầu vào: nums = [6, 6, 1]k = 3
Đầu ra: [6]
Giải thích: Khi k bằng độ dài của mảng (array), chỉ có một cửa sổ, chính là toàn bộ mảng. Giá trị lớn nhất là 6; bản sao thứ hai của 6 không tạo thêm đáp án thứ hai.

Câu hỏi mở rộng

Bạn có thể xây dựng một hàng đợi hỗ trợ thêm giá trị vào cuối, xóa giá trị ở đầu và đọc giá trị lớn nhất hiện tại, mỗi thao tác đều có thời gian khấu hao O(1) không?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Các cửa sổ liền kề dùng chung k-1 giá trị, nên việc tính lại giá trị lớn nhất sẽ lặp lại gần như toàn bộ công việc. Nhưng không thể hoàn tác một giá trị lớn nhất: khi giá trị lớn nhất trượt ra ngoài, bạn cần tìm giá trị lớn thứ hai mà không phải đọc lại cửa sổ. Hàng đợi hai đầu đơn điệu (monotonic deque) chỉ giữ lại những giá trị vẫn có thể trở thành giá trị lớn nhất, với đáp án nằm ở đầu hàng đợi.

Quét mọi cửa sổ

Đúng, nhưng không chạy xong với các test lớn nhất

Ý tưởng

Đọc các giá trị k trong từng cửa sổ và giữ lại giá trị lớn nhất. Bạn đọc toàn bộ mỗi cửa sổ nên sẽ không bỏ sót giá trị lớn nhất của cửa sổ đó. Mỗi cửa sổ trong số n-k+1 cửa sổ cần đọc k lần. Trường hợp tệ nhất là khi k xấp xỉ một nửa n: n = 2 × 10^4 và k = 10^4 tạo ra khoảng 10^4 cửa sổ, mỗi cửa sổ có 10^4 giá trị, tổng cộng 10^8 lần đọc.

Thuật toán

Lặp start từ 0 đến n-k.
Lấy giá trị lớn nhất trong các giá trị từ nums[start] đến nums[start+k-1].
Thêm giá trị đó vào kết quả và trả về kết quả sau vòng lặp.

def maxSlidingWindow(nums, k):
    result = []
    for start in range(len(nums) - k + 1):
        # Read all k values of this window again
        result.append(max(nums[i] for i in range(start, start + k)))
    return result

Các khối có giá trị lớn nhất ở mỗi phía

Ý tưởng

Chia mảng thành các khối có độ dài k: chỉ số từ 0 đến k-1, tiếp theo từ k đến 2k-1, cứ thế tiếp tục; khối cuối cùng sẽ ngắn hơn nếu k không chia hết cho n. Một cửa sổ có độ dài đúng bằng k, nên nó là một khối nguyên vẹn hoặc gồm phần cuối của khối này và phần đầu của khối tiếp theo.

Vì vậy, hãy tính trước fromStart[i], giá trị lớn nhất từ đầu khối chứa i đến i, và toEnd[i], giá trị lớn nhất từ i đến cuối khối đó. Cửa sổ bắt đầu tại i kết thúc ở i+k-1: toEnd[i] bao quát phần bên trái và fromStart[i+k-1] bao quát phần bên phải, nên giá trị lớn hơn trong hai giá trị đó là giá trị lớn nhất của cửa sổ. Trong ví dụ đầu tiên, cửa sổ [2, 12, 3] lấy toEnd[1] = 12 và fromStart[3] = 3, cho kết quả là 12.

Ba lượt duyệt có độ phức tạp thời gian O(n), đổi lại cần hai mảng phụ có độ dài n và cần có toàn bộ mảng trước khi đưa ra câu trả lời đầu tiên.

Thuật toán

Điền fromStart từ trái sang phải, bắt đầu lại bằng nums[i] khi i là bội số của k.
Điền toEnd từ phải sang trái, bắt đầu lại bằng nums[i] ở chỉ số cuối cùng và tại những vị trí mà i+1 là bội số của k.
Với mỗi chỉ số bắt đầu i từ 0 đến n-k, thêm giá trị lớn hơn trong toEnd[i] và fromStart[i+k-1].

def maxSlidingWindow(nums, k):
    n = len(nums)
    # Cut nums into blocks of k: indices 0..k-1, k..2k-1, and so on.
    from_start = [0] * n  # max from the start of i's block up to i
    to_end = [0] * n      # max from i up to the end of i's block
    for i in range(n):
        if i % k == 0:
            from_start[i] = nums[i]
        else:
            from_start[i] = max(from_start[i - 1], nums[i])
    for i in range(n - 1, -1, -1):
        if i == n - 1 or (i + 1) % k == 0:
            to_end[i] = nums[i]
        else:
            to_end[i] = max(to_end[i + 1], nums[i])
    # A window [i, i+k-1] is the tail of one block plus the head of the next.
    return [max(to_end[i], from_start[i + k - 1]) for i in range(n - k + 1)]

Deque đơn điệu chứa các chỉ số

Ý tưởng

Nếu chỉ số j đứng trước i và nums[j] ≤ nums[i], thì j không thể là giá trị lớn nhất nữa: mọi cửa sổ về sau có j cũng đều có i, mà i rời khỏi cửa sổ muộn hơn. Vì vậy, khi i xuất hiện, bạn có thể bỏ qua j.

Giữ một deque gồm các chỉ số chưa bị bỏ qua. Khi i xuất hiện, lấy các chỉ số ở cuối deque ra chừng nào giá trị của chúng còn nhỏ hơn hoặc bằng nums[i], rồi thêm i vào. Các giá trị còn lại giảm nghiêm ngặt từ đầu đến cuối, nên phần tử đầu tiên là giá trị lớn nhất trong cửa sổ. Hãy lưu chỉ số, vì phần tử đầu tiên cũng phải rời khỏi deque khi cửa sổ trượt qua nó. Trong ví dụ đầu tiên, tại chỉ số 5, deque chứa 12, 8 và 5; 12 nằm ở chỉ số 5 - 3 = 2, nên nó rời khỏi deque và đáp án là 8.

Mỗi chỉ số được thêm vào một lần và bị lấy ra nhiều nhất một lần: có nhiều nhất 2n thao tác với deque, thời gian O(n). Deque không bao giờ chứa nhiều hơn k chỉ số.

Thuật toán

Với mỗi chỉ số i, lấy các chỉ số ở cuối ra khi deque không rỗng và giá trị ở cuối của nó nhỏ hơn hoặc bằng nums[i].
Đưa i vào cuối.
Nếu chỉ số ở đầu bằng i-k, chỉ số đó đã ra khỏi cửa sổ: lấy nó ra.
Khi i ≥ k-1, thêm giá trị tại chỉ số ở đầu vào kết quả.

from collections import deque


def maxSlidingWindow(nums, k):
    window = deque()  # indices; their values strictly decrease from front to back
    result = []
    for i, x in enumerate(nums):
        # A value at the back that is not bigger than x can never be a maximum again.
        while window and nums[window[-1]] <= x:
            window.pop()
        window.append(i)
        # The front index has slid out of the window on the left.
        if window[0] == i - k:
            window.popleft()
        # From index k-1 on, every step completes a window; its maximum sits at the front.
        if i >= k - 1:
            result.append(nums[window[0]])
    return result

Lỗi thường gặp và trường hợp biên

Lưu giá trị thay vì chỉ số. Với [3, 1, 3] và k = 2, số 3 thứ hai đẩy số 3 đầu tiên ra khỏi deque, rồi chính nó cũng bị loại vì nó bằng nums[0], giá trị đã rời khỏi cửa sổ.
Trả lời quá sớm hoặc quá muộn. Cửa sổ đầy đầu tiên kết thúc ở chỉ số k-1, và kết quả phải chứa đúng n-k+1 giá trị.
Loại bỏ i-k+1 thay vì i-k. Chỉ số đó vẫn là giá trị đầu tiên của cửa sổ.
Đọc phần tử cuối của deque mà không kiểm tra xem deque có phần tử nào hay không.
Trong cách tiếp cận theo khối, quên rằng khối cuối cùng có thể ngắn hơn k. Lượt duyệt từ phải sang trái phải bắt đầu lại ở chỉ số cuối cùng cũng như ở cuối mỗi khối.

Câu hỏi thường gặp3

Độ phức tạp thời gian của bài toán tìm giá trị lớn nhất trong cửa sổ trượt là bao nhiêu?

Lời giải bằng deque đơn điệu chạy trong thời gian O(n), vì mỗi chỉ số được thêm vào một lần và bị loại ra nhiều nhất một lần. Deque chứa tối đa k chỉ số, nên ngoài phần kết quả, cần thêm O(k) bộ nhớ.

Có thể giải bài toán giá trị lớn nhất trong cửa sổ trượt bằng heap không?

Có. Đưa từng cặp giá trị và chỉ số vào một đống tối đa, rồi trước khi đọc phần tử trên cùng, hãy lấy nó ra khỏi đống nếu chỉ số nằm ngoài cửa sổ. Cách này chạy trong thời gian O(n log n) và có thể chứa tối đa n phần tử. Hàng đợi hai đầu nhanh hơn và nhỏ gọn hơn vì loại bỏ các giá trị không cần thiết ngay khi có giá trị lớn hơn xuất hiện.

Sự khác nhau giữa hàng đợi hai đầu đơn điệu và ngăn xếp đơn điệu là gì?

Đầu sau của deque hoạt động như một ngăn xếp đơn điệu: trước khi đẩy một giá trị vào, bạn loại bỏ những giá trị mà nó khiến trở nên vô dụng. Deque có thêm lối ra ở đầu trước dành cho những giá trị đã quá cũ. Phần tử lớn hơn tiếp theo không hết hạn, nên chỉ cần ngăn xếp. Đảo chiều phép so sánh, deque sẽ cho biết giá trị nhỏ nhất trong mỗi cửa sổ.

def maxSlidingWindow(nums, k):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

nums = [4, 2, 12, 3, 8, 5, 1]
k = 3

Đầu ra mong đợi

[12, 12, 12, 8, 8]

Sliding Window Maximum

Hàm

Ràng buộc

Ví dụ

Gợi ý

Lời giải

Quét mọi cửa sổ

Các khối có giá trị lớn nhất ở mỗi phía

Deque đơn điệu chứa các chỉ số

Lỗi thường gặp và trường hợp biên

Câu hỏi thường gặp3

Bài tập tương tự