Coding Interview Prep · Урок

N последовательных строк, соответствующих условию

Классический шаблон окна: «три последовательных дня с продажами выше X»

«N последовательных строк, соответствующих условию» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 3 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.

Классическая задача LeetCode

Это одна из наиболее часто встречающихся задач на собеседованиях по базам данных: "Найдите все даты, для которых продажи превышали порог как минимум в течение трёх последовательных дней," или популярная задача LeetCode: "Выведите стадион, где посещаемость превышала 100 в 3 и более последовательных строках."

Структура всегда одна и та же: строка подходит, только если она находится внутри серии из N последовательных строк, подходящих условию. В этом уроке показаны два понятных решения и ловушка, в которую попадает большинство кандидатов.

Пример данных

Мы используем ежедневную таблицу sales. Условие задаётся выражением amount > 100. Нужно вернуть каждый день, входящий в серию из 3 или более последовательных календарных дней, для которых выполнено это условие.

sale_date — одна строка на каждый день
amount — общая сумма продаж за этот день

Важная тонкость: строки должны быть последовательными в порядке, а в вариантах, основанных на датах, — также и в календаре.

SELECT * FROM sales ORDER BY sale_date;
-- sale_date  | amount
-- 2024-03-01 |  120
-- 2024-03-02 |  150
-- 2024-03-03 |  130
-- 2024-03-04 |   90
-- 2024-03-05 |  200

Подход 1: фильтрация, затем острова

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

Первый шаг — фильтр WHERE. На втором шаге повторно используется якорь метода разрывов и островов. Поскольку фильтрация выполнена заранее, остров здесь означает "серию последовательных дней, подходящих условию".

WITH qualifying AS (
  SELECT sale_date
  FROM sales
  WHERE amount > 100
)
SELECT * FROM qualifying ORDER BY sale_date;

Построение якоря подходящих серий

Пронумеруйте подходящие строки по дате и выполните вычитание, чтобы получить якорь острова. Строки, которые идут последовательно в календаре AND все подходят условию, будут иметь один якорь; неподходящий день удалён, поэтому серия прерывается именно там, где должна.

WITH qualifying AS (
  SELECT sale_date
  FROM sales
  WHERE amount > 100
),
numbered AS (
  SELECT sale_date,
    ROW_NUMBER() OVER (ORDER BY sale_date) AS rn
  FROM qualifying
)
SELECT sale_date, sale_date - rn AS grp
FROM numbered;

Оставляем достаточно длинные острова

Сгруппируйте данные по якорю, подсчитайте строки и оставьте только группы с COUNT(*) >= 3. Если интервьюеру нужны сами подходящие даты, присоедините сохранённые якоря к пронумерованным строкам.

WITH qualifying AS (
  SELECT sale_date FROM sales WHERE amount > 100
),
numbered AS (
  SELECT sale_date,
    ROW_NUMBER() OVER (ORDER BY sale_date) AS rn
  FROM qualifying
),
islands AS (
  SELECT sale_date - rn AS grp, COUNT(*) AS len
  FROM numbered
  GROUP BY sale_date - rn
  HAVING COUNT(*) >= 3
)
SELECT n.sale_date
FROM numbered n
JOIN islands i ON n.sale_date - n.rn = i.grp
ORDER BY n.sale_date;

Подход 2: скользящее окно COUNT

Более изящный подход, когда N мало и задано заранее: используйте оконный фрейм, чтобы подсчитать, сколько соседних строк также подходят условию. Если какое-либо окно из N последовательных строк, содержащее данную строку, полностью подходит условию, эта строка входит в ответ.

Сначала добавьте логический флаг, затем просуммируйте этот флаг по скользящим фреймам.

SELECT sale_date, amount,
  CASE WHEN amount > 100 THEN 1 ELSE 0 END AS ok
FROM sales;

Суммирование по трём фреймам

Для серии ровно из 3 строк подходящая строка входит в ответ, если сумма в трёхстрочном окне, заканчивающемся на этой строке, центрированном на ней или начинающемся с неё, равна 3. Вычислите три скользящие суммы и проверьте, равна ли какая-либо из них 3.

Именно эта техника лежит в основе решения задачи LeetCode 601 («Посещаемость стадиона»).

WITH flagged AS (
  SELECT sale_date, amount,
    CASE WHEN amount > 100 THEN 1 ELSE 0 END AS ok
  FROM sales
),
w AS (
  SELECT *,
    SUM(ok) OVER (ORDER BY sale_date
      ROWS BETWEEN 2 PRECEDING AND CURRENT ROW) AS s_end,
    SUM(ok) OVER (ORDER BY sale_date
      ROWS BETWEEN 1 PRECEDING AND 1 FOLLOWING) AS s_mid,
    SUM(ok) OVER (ORDER BY sale_date
      ROWS BETWEEN CURRENT ROW AND 2 FOLLOWING) AS s_start
  FROM flagged
)
SELECT sale_date, amount
FROM w
WHERE ok = 1 AND (s_end = 3 OR s_mid = 3 OR s_start = 3);

Ловушка календарных пропусков

Подход со скользящей суммой использует ROWS, который считает соседние строки результата, а не соседние календарные дни. Если неподходящий день уже отфильтрован, две строки могут оказаться соседними в результате, но не быть последовательными в календаре.

Вывод: применяйте скользящее окно к полному ежедневному ряду (не фильтруйте его заранее) либо используйте метод якоря по датам, который естественным образом учитывает календарные пропуски. На собеседовании явно проговорите этот компромисс.

Обобщение для любого N

Подход 1 (фильтрация, затем острова) обобщается без труда: просто измените HAVING COUNT(*) >= N. В этом его главное преимущество перед суммой по нескольким окнам, для которой при росте N требуется добавлять новые фреймы.

Для параметризованного или большого N отдавайте предпочтение методу островов — здесь нужно изменить один порог, а не вручную прописывать N−1 окон.

-- only the threshold changes for N = 5
HAVING COUNT(*) >= 5

Выбор подхода

Краткое руководство, которое можно озвучить:

Фильтрация, затем острова: учитывает календарные пропуски, обобщается для любого N и возвращает полные серии — безопасный вариант по умолчанию.
Сумма по скользящему окну: изящна для небольшого фиксированного N в плотном ежедневном ряду, но следите за ловушкой несоответствия ROWS календарю.

Назвать оба подхода, а затем обосновать свой выбор — именно это ценят интервьюеры, нанимающие специалистов среднего и высокого уровня.

Полное решение

Переносимый ответ для любого N, учитывающий последовательность календарных дат и возвращающий подходящие даты:

WITH qualifying AS (
  SELECT sale_date FROM sales WHERE amount > 100
),
numbered AS (
  SELECT sale_date,
    ROW_NUMBER() OVER (ORDER BY sale_date) AS rn
  FROM qualifying
),
islands AS (
  SELECT sale_date - rn AS grp, COUNT(*) AS len
  FROM numbered
  GROUP BY sale_date - rn
  HAVING COUNT(*) >= 3
)
SELECT n.sale_date
FROM numbered n
JOIN islands i ON n.sale_date - n.rn = i.grp
ORDER BY n.sale_date;

Быстрая проверка

Найдите тонкую ошибку.

Итоги

Для N последовательных строк, удовлетворяющих условию:

Фильтрация, затем острова: оставьте подходящие строки, постройте якорь с помощью date - ROW_NUMBER(), сгруппируйте данные и используйте HAVING COUNT(*) >= N. Подход обобщается и учитывает календарные пропуски.
Сумма по скользящему окну: пометьте строки и просуммируйте их по фиксированным фреймам из N строк; подход изящен, но в предварительно отфильтрованных данных остерегайтесь несоответствия ROWS календарю.

Далее: вычисление текущей активной серии пользователя на сегодняшний день.

Часто задаваемые вопросы

Урок «N последовательных строк, соответствующих условию» бесплатный?

Да — полный текст урока «N последовательных строк, соответствующих условию» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.

Чему я научусь в уроке «N последовательных строк, соответствующих условию»?

Классический шаблон окна: «три последовательных дня с продажами выше X» Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.

Нужен ли мне опыт, чтобы начать Coding Interview Prep?

Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 3 из 4.

Сколько времени занимает урок «N последовательных строк, соответствующих условию»?

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

Можно ли писать и запускать код в этом уроке Coding Interview Prep?

Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.

Все уроки этого курса

Поиск последовательных календарных дней
Самая длинная серия для пользователя
N последовательных строк, соответствующих условию
Текущая активная серия на сегодня

← Назад к Coding Interview Prep