Sliding Window

В тази секция ще разгледаме няколко задачи, решавани с метода на "плъзгащия се прозорец" ("Sliding Window"). Тази техника е популярна както в състезателни задачи, така и в задачи от интервюта за работа (макар и там обикновено да са значително по-лесни). Основната идея е да се възползваме от това, че даден интервал, който ни интересува, се променя относително малко (при това - само в началото и края, но не и средните елементи). В този случай можем да ползваме някаква структура данни в която да пазим важната за нас информация от подинтервала и да поддържаме бързо питане за функцията, която ни интересува (например сума, брой на някакви специални елементи, или нещо друго). Обикновено това, че интервалът се променя относително малко, ни позволява да преизползваме някаква информация от предходните query-та или търсения, без да се налага да я изчисляваме наново. Това може драстично да оптимизира алгоритъма, като свежда сложността на части от наивната имплементация от линейна до логаритмична или дори константна.

Подходяща тема, която можете да разгледате, е Плъзгащ се прозорец.

Задачите в секцията имат наивно, бавно решение, и бързо решение, базирано на "плъзгащ се прозорец". Много състезатели ползват наивното решение за да тестват бързото (с малки "рандом" тестове).