Пересекающиеся окна

В уроке ты:

Разберешь задачу с собеседования в BigTech
Научишься применять паттерн "пересекающиеся плавающие окна", чтобы решать задачи на собеседовании с первой попытки
Научишься оценивать время и память алгоритмов с использованием этого паттерна

Пример задачи с собеседования

Ты уже освоил паттерн "непересекающиеся окна", но есть и более сложные задачи на плавающие окна. Давай рассмотрим условие одной из них, где изученного ранее паттерна будет недостаточно.

Условие

Дан массив nums, состоящий только из нулей и единиц. Нужно вернуть максимальное число подряд идущих единиц при условии, что можно заменить один ноль на единицу.

Пример

Ввод: nums = [1,0,1,1,1,0,0,1,1]
Вывод: 5
Объяснение: нужно заменить первый ноль на единицу.

В чем сложность задачи

Давай выделим все потенциальные подмассивы, которые могут нас интересовать. Мы получим следующие подмассивы, содержащие не более одного нуля: [1,0,1,1,1], [1,1,1,0], [0], [0,1,1]. Можно заметить, что эти подмассивы пересекаются, и поэтому не получится использовать ранее изученный паттерн "непересекающиеся окна".

Общий алгоритм решения

Мы будем действовать по следующему алгоритму: заведём два указателя l и r, где l указывает на начало плавающего окна, а r — на его конец (включительно).

Будем двигать правый указатель r вправо, пока r + 1 меньше длины массива и либо элемент nums[r+1] равен 1 , либо количество нулей в окне zerosCount меньше 1. То есть, пока можем добавить следующий элемент в окно.
Если при сдвиге правого указателя встречаем ноль и он единственный в окне, то запоминаем его индекс в zeroIdx и увеличиваем zerosCount.
Если не можем двигать правый указатель, значит достигнут максимальный размер окна при текущем l. Обновляем ответ: result = max(result, windowSize), где windowSize = r - l + 1.
Сдвигаем левый указатель l на 1 вправо и, если элемент nums[l] был нулём, уменьшаем zerosCount. Это позволяет нам передвинуть окно и продолжить поиск.
Повторяем шаги 1–4, пока левый указатель l не достигнет конца массива.

Код

using System;
using System.Collections.Generic;

public class Solution
{
    public static int LongestSubset(List<int> stock)
    {
        int l = 0, r = 0;
        int result = 0;
        int zerosCount = (stock[0] == 0) ? 1 : 0;
        int zeroIdx = 0;

        while (l < stock.Count)
        {
            while (r + 1 < stock.Count && (stock[r + 1] == 1 || zerosCount < 1))
            {
                if (stock[r + 1] == 0)
                {
                    zerosCount++;
                    zeroIdx = r + 1;
                }
                r++;
            }

            // обновляем ответ
            int windowSize = r - l + 1;
            result = Math.Max(result, windowSize);

            // Сдвигаем левый указатель
            zerosCount = 0;
            l = Math.Max(zeroIdx + 1, l + 1);
        }
        return result;
    }
}

#include <vector>
#include <algorithm>

class Solution {
public:
    int longestSubset(std::vector<int>& stock) {
        int l = 0, r = 0;
        int result = 0;
        int zerosCount = (stock[0] == 0) ? 1 : 0;
        int zeroIdx = 0;

        while (l < stock.size()) {
            while (r + 1 < stock.size() && (stock[r + 1] == 1 || zerosCount < 1)) {
                if (stock[r + 1] == 0) {
                    zerosCount++;
                    zeroIdx = r + 1;
                }
                r++;
            }

            // обновляем ответ
            int windowSize = r - l + 1;
            result = std::max(result, windowSize);

            // Сдвигаем левый указатель
            zerosCount = 0;
            l = std::max(zeroIdx + 1, l + 1);
        }
        return result;
    }
};

func longestSubset(stock []int) int {
    l, r := 0, 0
    result := 0
    zerosCount := 0
    if stock[0] == 0 {
        zerosCount = 1
    }
    zeroIdx := 0

    for l < len(stock) {
        for r+1 < len(stock) && (stock[r+1] == 1 || zerosCount < 1) {
            if stock[r+1] == 0 {
                zerosCount++
                zeroIdx = r + 1
            }
            r++
        }

        // обновляем ответ
        windowSize := r - l + 1
        result = max(result,windowSize)

        // Сдвигаем левый указатель
        zerosCount = 0
        l = max(zeroIdx + 1, l + 1)
    }
    return result
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

import java.util.List;

public class Solution {
    public static int longestSubset(List<Integer> stock) {
        int l = 0, r = 0;
        int result = 0;
        int zerosCount = (stock.get(0) == 0) ? 1 : 0;
        int zeroIdx = 0;

        while (l < stock.size()) {
            while (r + 1 < stock.size() && (stock.get(r + 1) == 1 || zerosCount < 1)) {
                if (stock.get(r + 1) == 0) {
                    zerosCount++;
                    zeroIdx = r + 1;
                }
                r++;
            }

            // обновляем ответ
            int windowSize = r - l + 1;
            result = Math.max(result, windowSize);

            // Сдвигаем левый указатель
            zerosCount = 0;
            l = Math.max(zeroIdx + 1, l + 1);
        }
        return result;
    }
}

from typing import *

def longestSubset(stock: List[int]) -> int:
    l = 0
    r = 0
    result = 0
    zerosCount = stock[0] == 0
    zeroIdx = 0

    while l < len(stock):
        while r + 1 < len(stock) and (stock[r + 1] == 1 or zerosCount < 1):
            if stock[r + 1] == 0:
                zerosCount += 1
                zeroIdx = r + 1
            r += 1
        
        # обновляем ответ
        windowSize = r - l + 1
        result = max(result, windowSize)

        # сдвигаем на zeroIdx, когда у нас есть 0 в окне
        # сдвигаем на l + 1, если нулей в окне нет (нужно, чтобы не зациклиться)
        zerosCount = 0
        l = max(zeroIdx + 1, l + 1)
    return result

function longestSubset(stock) {
    let l = 0;
    let r = 0;
    let result = 0;
    let zerosCount = stock[0] === 0 ? 1 : 0;
    let zeroIdx = 0;

    while (l < stock.length) {
        while (r + 1 < stock.length && (stock[r + 1] === 1 || zerosCount < 1)) {
            if (stock[r + 1] === 0) {
                zerosCount++;
                zeroIdx = r + 1;
            }
            r++;
        }

        // обновляем ответ
        const windowSize = r - l + 1;
        result = Math.max(result, windowSize);

        // Сдвигаем левый указатель
        zerosCount = 0;
        l = Math.max(zeroIdx + 1, l + 1);
    }
    return result;
}

Оценка по времени и памяти

Казалось бы, в коде у нас цикл в цикле и сложность будет квадратичная, но не все так просто! Дело в том, что несмотря на то, что есть вложенный цикл, мы на каждом шаге двигаем указатель l и r только вперед как минимум на 1 шаг.

Cуммарно получается, что левый указатель полностью пробегается по массиву и правый указатель пробегается по массиву. Если размер массива n, то получается 2*n действий. В BigO нотации константы опускаются, поэтому оценка по времени будет O(n)

Дополнительную память мы не выделяем, поэтому она константна и оценивается как O(1). Итог:

Время: O(n)
Память: O(1)

Паттерн “пересекающиеся плавающие окна”

Чтобы каждый раз не придумывать решение для новой задачи на “пересекающиеся окна”, можно следовать паттерну:

using System;
using System.Collections.Generic;

public class Solution
{
    public static List<string> Calculate(List<int> nums)
    {
        int l = 0;
        int r = -1; // Обратите внимание, что r = -1
        
         List<string> result = new List<string>();
        // Здесь можно добавить другие переменные, если они используется в вашем коде

        while (l < nums.Count)
        {
            while (r + 1 < nums.Count && /* здесь условие, что следующий элемент можно взять в окно */)
            {
                // возможна дополнительная обработка ...
                r++;
            }

            // обновляем ответ
            // ...

            // обновляем состояние плавающего окна перед сдвигом
            // ...

            // сдвигаем левый указатель
            l++;
        }
        return result;
    }

}

#include <vector>
#include <string>

using namespace std;

vector<string> calculate(const vector<int>& nums) {
    int l = 0;
    int r = -1; // Обратите внимание, что r = -1
    vector<string> result; // Объявляем результат

    // Здесь можно добавить другие переменные, если они используется в вашем коде

    while (l < nums.size()) {
        while (r + 1 < nums.size() && /* здесь условие, что следующий элемент можно взять в окно */) {
            // возможна дополнительная обработка ...
            r++;
        }

        // обновляем ответ
        // ...

        // обновляем состояние плавающего окна перед сдвигом
        // ...

        // сдвигаем левый указатель
        l++;
    }
    return result;
}

package main

import (
    "fmt"
)

func calculate(nums []int) []string {
    l := 0
    r := -1 // Обратите внимание, что r = -1
    var result []string // Объявляем результат

    // Здесь можно добавить другие переменные, если они используется в вашем коде

    for l < len(nums) {
        for r+1 < len(nums) && /* здесь условие, что следующий элемент можно взять в окно */ {
            // возможна дополнительная обработка ...
            r++
        }

        // обновляем ответ
        // ...

        // обновляем состояние плавающего окна перед сдвигом
        // ...

        // сдвигаем левый указатель
        l++
    }
    return result
}

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public static List<String> calculate(List<Integer> nums) {
        int l = 0;
        int r = -1; // Обратите внимание, что r = -1
        
        List<String> result = new ArrayList<>(); // Объявляем результат
        // Здесь можно добавить другие переменные, если они используются в вашем коде

        while (l < nums.size()) {
            while (r + 1 < nums.size() && /* здесь условие, что следующий элемент можно взять в окно */) {
                // возможна дополнительная обработка ...
                r++;
            }

            // обновляем ответ
            // ...

            // обновляем состояние плавающего окна перед сдвигом
            // ...

            // сдвигаем левый указатель
            l++;
        }
        return result;
    }
}

from typing import *

def calculate(nums: List[int]) -> List[str]:
    l = 0
    # обрати внимание, что r = -1
    r = -1
    # Здесь можно добавить другие переменные, если они используются в вашем коде
    while l < len(nums):
        while r + 1 < len(counter) and # тут условие, что следующий элемент можно взять в окно
            # возможна дополнительная обработка ...
            r += 1

        # обновляем ответ
        # ...
        
        # обновляем состояние плавающего окна перед сдвигом
        # ...

        # сдвигаем левый указатель
        l += 1
    return result

function calculate(nums) {
    let l = 0;
    let r = -1; // Обратите внимание, что r = -1

    const result = []; // Объявляем результат
    // Здесь можно добавить другие переменные, если они используются в вашем коде

    while (l < nums.length) {
        while (r + 1 < nums.length && /* здесь условие, что следующий элемент можно взять в окно */) {
            // возможна дополнительная обработка ...
            r++;
        }

        // обновляем ответ
        // ...

        // обновляем состояние плавающего окна перед сдвигом
        // ...

        // сдвигаем левый указатель
        l++;
    }
    return result;
}

Для данного паттерна действуют следующие правила:

Начальное положение указателей чаще всего l = 0, а r = -1 – это сделано, чтобы добавление первого элемента в плавающее окно делалось не отдельно, а согласно общему алгоритму
Сдвиг правого указателя не нарушает правила плавающего окна и всегда формирует такое окно, на основании которого можно получить верный ответ
Обновление ответа происходит после сдвига правого указателя максимально далеко
Левый указатель сдвигается всегда на 1, что позволяет рассмотреть все возможные не пересекающиеся окна

Решение на основе паттерна

using System;
using System.Collections.Generic;

public class Solution
{
    public static int LongestSubset(List<int> stock)
    {
        int l = 0;
        // r = -1, чтобы добавление первого элемента не было исключением
        int r = -1;
        int result = 0;
        int zerosCount = 0;

        while (l < stock.Count)
        {
            while (r + 1 < stock.Count && (stock[r + 1] == 1 || zerosCount < 1))
            {
                zerosCount += stock[r + 1] == 0 ? 1 : 0;
                r++;
            }
            // обновляем ответ
            int windowSize = r - l + 1;
            result = Math.Max(result, windowSize);

            if (stock[l] == 0)
            {
                zerosCount--;
            }
            l++;
        }
        return result;
    }
}

#include <vector>
#include <algorithm>

class Solution {
public:
    int longestSubset(std::vector<int>& stock) {
        int l = 0;
        // r = -1, чтобы добавление первого элемента не было исключением
        int r = -1;
        int result = 0;
        int zerosCount = 0;

        while (l < stock.size()) {
            while (r + 1 < stock.size() && (stock[r + 1] == 1 || zerosCount < 1)) {
                zerosCount += (stock[r + 1] == 0) ? 1 : 0;
                r++;
            }
            // обновляем ответ
            int windowSize = r - l + 1;
            result = std::max(result, windowSize);

            if (stock[l] == 0) {
                zerosCount--;
            }
            l++;
        }
        return result;
    }
};

package main

import "math"

func longestSubset(stock []int) int {
    // r = -1, чтобы добавление первого элемента не было исключением
    l, r := 0, -1
    result, zerosCount := 0, 0

    for l < len(stock) {
        for r+1 < len(stock) && (stock[r+1] == 1 || zerosCount < 1) {
            if stock[r+1] == 0 {
                zerosCount++
            }
            r++
        }
        // обновляем ответ
        windowSize := r - l + 1
        result = int(math.Max(float64(result), float64(windowSize)))

        if stock[l] == 0 {
            zerosCount--
        }
        l++
    }
    return result
}

import java.util.List;

public class Solution {
    public static int longestSubset(List<Integer> stock) {
        int l = 0;
        // r = -1, чтобы добавление первого элемента не было исключением
        int r = -1;
        int result = 0;
        int zerosCount = 0;

        while (l < stock.size()) {
            while (r + 1 < stock.size() && (stock.get(r + 1) == 1 || zerosCount < 1)) {
                zerosCount += (stock.get(r + 1) == 0) ? 1 : 0;
                r++;
            }
            // обновляем ответ
            int windowSize = r - l + 1;
            result = Math.max(result, windowSize);

            if (stock.get(l) == 0) {
                zerosCount--;
            }
            l++;
        }
        return result;
    }
}

def longestSubset(stock: List[int]) -> int:
    l = 0
    # r = -1, чтобы добавление первого элемента не было исключением
    r = -1
    result = 0
    zerosCount = 0

    while l < len(stock):
        while r + 1 < len(stock) and (stock[r + 1] == 1 or zerosCount < 1):
            zerosCount += int(stock[r + 1] == 0)
            r += 1
        
        # обновляем ответ
        windowSize = r - l + 1
        result = max(result, windowSize)

        if stock[l] == 0:
            zerosCount -= 1
        l = l + 1
    return result

function longestSubset(stock) {
    let l = 0;
    // r = -1, чтобы добавление первого элемента не было исключением
    let r = -1;
    let result = 0;
    let zerosCount = 0;

    while (l < stock.length) {
        while (r + 1 < stock.length && (stock[r + 1] === 1 || zerosCount < 1)) {
            zerosCount += stock[r + 1] === 0 ? 1 : 0;
            r++;
        }
        // обновляем ответ
        const windowSize = r - l + 1;
        result = Math.max(result, windowSize);

        if (stock[l] === 0) {
            zerosCount--;
        }
        l++;
    }
    return result;
}

Решение на основе паттерна оптимально с точки зрения асимптотики и время алгоритма O(n), а память O(1)

Всегда ли решать на основе паттерна

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

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

Что дальше?

С первого раза сложно понять, в чем смысл каждого из пунктов, поэтому не погружайся в самом начале в урок слишком глубоко. Если ты прочитал урок несколько раз и понял основной смысл, то скорее переходи к задачкам!

Именно задачи помогут отточить все навыки, и на конкретных примерах ты поймешь все нюансы, которые важно знать, чтобы на собеседовании решать задачи быстро и с первого раза!