Lesson 14 — Sliding Window (Cửa sổ trượt)
3 module tương tác: (1) Fixed window — trượt cửa sổ độ dài k, thấy tổng được tái dùng (trừ trái + cộng phải, không tính lại); (2) Variable window — longest substring không lặp, animate mở rộng/thu nhỏ theo hash; (3) Window maximum — deque đơn điệu giữ max của mỗi window.
Module 1 — Fixed window: tổng tái dùng
Mảng cố định k. Mỗi bước trượt: phần tử trái rơi ra, phần tử phải lọt vào. Tổng mới = tổng cũ − trái + phải (O(1)).
sum = —
max = —
Nhấn "Khởi tạo" rồi "Trượt một bước".
Module 2 — Variable window: longest substring không lặp
Mở rộng r mỗi bước. Nếu s[r] đã có trong window (gây lặp), nhảy l qua bản sao cũ (window co lại). Cập nhật độ dài lớn nhất.
best = —
Nhấn "Khởi tạo" rồi "Bước tiếp".
Module 3 — Window maximum: deque đơn điệu
Deque giữ chỉ số, giá trị giảm dần từ front→back. Push: bỏ các back ≤ giá trị mới. Bỏ front nếu trôi ra ngoài window. Front luôn là max của window.
Deque (giá trị giảm dần, lưu chỉ số):
rỗng
Kết quả (max mỗi window):
Nhấn "Khởi tạo" rồi "Bước tiếp".