Окно, которое меняет размер под правило

Tier 1Бесплатно

Elman HuseynovОбновлено 2026-10-21

Уровень

Где применяется

1. Задача

У клиента твоей платформы есть лимит расходов. Ты знаешь, сколько стоили его запросы за каждую минуту. Нужно найти самый длинный отрезок минут подряд, за который суммарная стоимость не вышла за лимит. Иначе говоря, самый долгий период, когда клиент уложился в бюджет.

В прошлом уроке ширина окна k была дана заранее. Здесь её никто не даёт. Длина отрезка и есть то, что ты ищешь. Окно заданной ширины тут не подойдёт, потому что ширина неизвестна.

Решение в лоб перебирает каждое начало. От каждой стартовой минуты оно идёт вперёд, пока сумма не превысит лимит, и записывает длину. Это O(n²), цикл внутри цикла, а поток данных может быть огромным.

2. Простыми словами

На этот раз никто не говорит, какой ширины должен быть отрезок. Ширину ты и ищешь: самый длинный отрезок, который ещё выполняет правило, например укладывается в бюджет.

Возьми числа 2, 3, 1, 2, 4 и лимит 7. Ты добавляешь числа справа по одному: 2, потом 3, потом 1. Сумма 6, в лимит укладываемся, в окне 3 числа. Добавляешь 2, сумма 8, это больше 7. Тогда убираешь числа слева, пока сумма снова не уложится: убрал 2, сумма 6. На каждом шаге записываешь, сколько чисел в окне, и запоминаешь самое большое количество. Каждое число добавляется один раз и убирается не больше одного раза.

3. Идея

Держи два маркера и сумму окна. Маркер right растит окно: берёт следующий элемент и прибавляет его к сумме. Как только сумма нарушает правило, маркер left сужает окно с начала: вычти nums[left], сдвинь left вперёд и повторяй, пока правило снова не выполнится. После каждого шага окно от left до right укладывается в правило, поэтому записывай его длину.

Всё это стоит O(n), потому что left движется только вперёд и никогда не возвращается. Возвращаться ему не нужно, потому что все числа здесь неотрицательные. Добавленное число может только увеличить сумму, а убранное слева может только уменьшить. Когда нарушение исправлено, возвращать убранные слева числа нет смысла: сумма от этого только вырастет.

Проследим «самый длинный отрезок с суммой ≤ 7» на [2, 3, 1, 2, 4].

right указывает на 2: сумма 2, длина 1.
right указывает на 3: сумма 5, длина 2.
right указывает на 1: сумма 6, длина 3.
right указывает на 2: сумма 8, это больше 7. Убираем 2 слева, сумма 6, left сдвигается вперёд. Окно [3, 1, 2], длина 3.
right указывает на 4: сумма 10, это больше 7. Убираем 3, сумма 7, left сдвигается вперёд. Окно [1, 2, 4], длина 3.

Лучшая длина 3.

4. Во что это обходится

Время O(n). right проходит список один раз. left за весь проход сдвигается в сумме не больше n раз. Всего выходит не больше 2n движений. Внутри for есть while, но это не вложенный перебор: while не начинает заново на каждом шаге right. Память O(1): два маркера и сумма.

5. Где это встречается

Самый долгий период, когда расход ресурсов или денег не превысил лимит. Самый длинный отрезок стабильной работы сервиса, пока доля ошибок держалась ниже порога. Самая длинная подстрока или часть массива, которая выполняет ограничение, при разборе текста и логов. Решения о буферизации вида «сколько данных держать в памяти, пока ограничение по размеру не заставит их сбросить». Любая задача «найти самый длинный отрезок потока, который выполняет условие» решается таким окном.

Самый длинный отрезок с суммой не больше 6

longestUnder([2, 1, 5, 1, 1, 2, 1], 6)

left

sum = 0limit = 6best = 0

Ищем самый длинный отрезок с суммой не больше 6. Окно пока пустое.

1 / 16

Гонка скорости

Самый длинный отрезок с суммой не больше 50 в одних и тех же 40 положительных числах

Столбики: 40 значений. Под предел помещается примерно четверть из них, и таблица ниже сохраняет эту долю.

Одна операция: одно чтение значения. За каждый кадр все дорожки делают одинаковое число операций, поэтому медленная отстаёт.

Перебор всех начал отрезка O(n²)

операций: 0

Растущее и сжимающееся окно O(n)

операций: 0

А если чисел больше

Операции для n чисел и примерное время при 100 миллионах простых операций в секунду. Это оценка по тому же счёту, а не замер.

n = 1 000

Перебор всех начал отрезка251 тыс. · 2,5 мс

Растущее и сжимающееся окно2 тыс. · меньше 1 мс

n = 100 000

Перебор всех начал отрезка2,5 млрд · 25 с

Растущее и сжимающееся окно200 тыс. · 2 мс

n = 10 000 000

Перебор всех начал отрезка25 трлн · 2,9 дн.

Растущее и сжимающееся окно20 млн · 200 мс

Как узнать

Скользящее окно (переменное) (Sliding window (variable))

Эти слова в условии значат этот паттерн

самый длинный/короткий непрерывный подмассив или подстрока
удовлетворяющий условию (сумма <= K, не более, без нарушения лимита)
не более K различных, без повторов, содержит все из X
непрерывный отрезок, не подпоследовательность

Похоже, но не то

Скользящее окно (фиксированный размер) (Sliding window (fixed size))
Фиксированное окно шириной k от первого шага до последнего. Это окно выбирает ширину само.
Два указателя (с концов) (Two pointers (opposite ends))
Те стартуют врозь на отсортированных данных и сходятся к паре. Здесь оба конца идут в одну сторону.
Префиксные суммы (Prefix sums)
Префиксные суммы работают с отрицательными числами и любыми диапазонами. Сужение же считает, что удаление помогает.
Хеш-множество / словарь (Hash set / map)
Словарь сам по себе описывает всю коллекцию. Окну нужны счётчики только для живого отрезка.

n до 1e6 и один лучший отрезок дают O(n). Каждый конец сдвигается не более n раз.

На LeetCode

Задачи, где нужен самый длинный или самый короткий отрезок подряд, который держит ограничение, а длина заранее неизвестна. Расширяй окно справа и сужай слева, пока ограничение нарушено.

209.Minimum Size Subarray Sum (откроется в новой вкладке)Средняя
Расширяй, пока сумма не дойдёт до target, потом сужай, пока она ещё держится, и запоминай самую короткую длину.
1004.Max Consecutive Ones III (откроется в новой вкладке)Средняя
В окне может быть не больше k нулей, поэтому сужай его, как только нулей стало больше.
1493.Longest Subarray of 1's After Deleting One Element (откроется в новой вкладке)Средняя
То же окно с местом для одного нуля, а ответ равен его длине минус один.
713.Subarray Product Less Than K (откроется в новой вкладке)Средняя
Храни произведение вместо суммы, и каждое подходящее окно добавляет right минус left плюс 1 новых подмассивов.

Твоя задача (Tier 1)

Напиши функцию longestSubarrayAtMost(nums, K).

Найди самый длинный отрезок чисел подряд, сумма которого не больше K. Расширяй окно справа и сужай слева каждый раз, когда сумма становится больше K.

Вход: nums, список неотрицательных чисел, и K, наибольшая допустимая сумма. Пример: [2, 3, 1, 2, 4], 7.
Возвращает: длину самого длинного отрезка, сумма которого не больше K.

Шаги:

Заведи маркер left = 0, сумму sum = 0 и лучшую длину best = 0.
Двигай right от начала списка до конца. На каждом шаге прибавляй nums[right] к sum.
Пока sum больше K, вычитай nums[left] из sum и сдвигай left на шаг вправо.
Теперь окно от left до right укладывается в лимит. Если его длина right - left + 1 больше best, обнови best. В конце верни best.

Готово, когда проходят все тесты:

[2, 3, 1, 2, 4], 7 -> 3
[1, 1, 1, 1], 2 -> 2
[1, 2], 100 -> 2 (укладывается весь список)
[10, 1, 1], 5 -> 2 (10 не укладывается никогда)
[5], 5 -> 1 (одно число, ровно на пределе)
[], 10 -> 0 (пустой список)
[9], 5 -> 0 (одно число, и оно уже больше предела)

Практика

longestSubarrayAtMost

longestSubarrayAtMost(nums, K) -> number (length of longest contiguous subarray with sum <= K; nums are non-negative)

export function longestSubarrayAtMost(nums, K) {
  // Your code here. The task is described in the box above the editor.
}

Ты здесь как гость

Тесты запускаются прямо здесь, без аккаунта. Код сохраняется только в этом браузере. Бесплатный аккаунт сохранит его на любом устройстве, отметит шаг пройденным и покажет, где ты в курсе.

Завести бесплатный аккаунт Войти

Лестница подсказок

Застрял? Открывай по одной, но сначала попробуй сам.

НазадПереиспользуем работу прошлого окна ДалееОкно, которое помнит своё содержимое