Mẫu mã: Cửa sổ trượt

Khi đối mặt với những thách thức về thuật toán, có một số mẫu cực kỳ hữu ích (Mẫu thuật toán, hay mô hình thuật toán, là một phương pháp, chiến lược hoặc kỹ thuật giải quyết một vấn đề) sẽ giúp cuộc sống của chúng ta dễ dàng hơn rất nhiều. “Cửa sổ trượt” là một mô hình giải quyết vấn đề phổ biến trong khoa học máy tính. Nó được sử dụng thường xuyên nhất trên mảng và chuỗi. Nguyên tắc chính đằng sau nó là tạo một “cửa sổ” và sau đó kiểm tra, nếu dữ liệu trong cửa sổ thỏa mãn điều kiện của vấn đề của bạn, cũng như chuyển đổi hai vòng lặp lồng nhau thành một vòng lặp duy nhất. Ở cuối bài viết này, bạn sẽ tìm thấy các tài nguyên hữu ích để giúp bạn với mẫu này.

từ khóa: Tìm giá trị nhỏ nhất, tối đa, ngắn nhất hoặc dài nhất.

Nhận repo của những ví dụ này: https://github.com/LuisSalas94/Sliding-Window-Pattern-Article

Ví dụ 01:

Báo cáo vấn đề

Cho một mảng, hãy tìm giá trị trung bình của tất cả các mảng con của "k" phần tử liền kề trong đó.

Mảng: [1, 3, 2, 6, -1, 4, 1, 8, 2], k = 5

Ở đây, chúng tôi được yêu cầu tìm giá trị trung bình của tất cả các mảng con của "5" phần tử liền kề trong mảng đã cho. Hãy giải quyết vấn đề này:

1. Đối với 5 số đầu tiên (mảng con từ chỉ số 0–4), giá trị trung bình là (1 + 3 + 2 + 6–1) / 5 => 2,2
2. Trung bình của 5 số tiếp theo (mảng con từ chỉ mục 1–5) là: (3 + 2 + 6–1 + 4) / 5 => 2,8
3. Đối với 5 mảng con tiếp theo (mảng con từ chỉ mục 2–6), trung bình: (2 + 6–1 + 4 + 1) / 5 => 2,4

Đầu ra: [2.2, 2.8, 2.4, 3.6, 2.8]

Một thuật toán brute-force sẽ tính toán tổng của mọi mảng con 5 phần tử của mảng đã cho và chia tổng cho “5” để tìm giá trị trung bình.

Có giải pháp nào tốt hơn không? Bạn có thấy bất kỳ hiệu quả nào trong cách tiếp cận trên không? Trên thực tế, có một giải pháp tốt hơn: Cách hiệu quả để giải quyết vấn đề này là hình dung mỗi mảng con như một cửa sổ trượt gồm các phần tử “5”. Điều này có nghĩa là chúng ta sẽ trượt cửa sổ theo một phần tử khi chúng ta chuyển sang mảng con tiếp theo. Để sử dụng lại tổng từ mảng con trước đó, chúng tôi sẽ trừ phần tử đi ra khỏi cửa sổ và thêm phần tử hiện đang được đưa vào cửa sổ trượt.

Ví dụ 02:

Báo cáo vấn đề

Cho một mảng các số dương và một số dương “k” tìm tổng lớn nhất của bất kỳ mảng con liền kề nào có kích thước là “k”.

Mảng: [2, 1, 5, 1, 3, 2], k = 3

Đối với điều này, hãy coi mỗi mảng con như một Cửa sổ trượt có kích thước “k”. Để tính tổng của mảng con tiếp theo, chúng ta cần phải trượt cửa sổ về phía trước một phần tử, Vì vậy, để trượt cửa sổ về phía trước và tính tổng của vị trí mới của cửa sổ trượt, cần có hai điều sau:

1. Trừ phần tử đi ra khỏi cửa sổ trượt, tức là trừ phần tử đầu tiên của cửa sổ.
2. Thêm phần tử mới được đưa vào cửa sổ trượt, tức là phần tử đến ngay sau phần cuối của cửa sổ.

Báo cáo vấn đề

Cho một mảng các số dương và một số dương “S”, hãy tìm độ dài của mảng con liền kề nhỏ nhất có tổng lớn hơn hoặc bằng “S”. Trả về 0 nếu không tìm thấy mảng con nào như vậy.

Mảng: [2, 1, 5, 2, 3, 2], S = 7

Kết quả: 2
Giải thích: Mảng con nhỏ nhất có tổng lớn hơn hoặc bằng '7' là [5, 2].

Chúng ta có thể sử dụng một chiến lược tương tự như đã thảo luận trong Dải con tổng tối đa của kích thước k. Tuy nhiên, có một điểm khác biệt: trong vấn đề này, kích thước cửa sổ trượt không cố định. Đây là cách chúng tôi sẽ giải quyết vấn đề này.

Điều đáng kinh ngạc về các bài toán Cửa sổ trượt là hầu hết thời gian chúng có thể được giải quyết trong thời gian O (N) và độ phức tạp không gian O (1) .