Задачи на структуры данных: подробный разбор с примерами

Почему задачи на структуры данных важны?

Задачи на структуры данных позволяют:

• 🧠 Развить алгоритмическое мышление и способность анализировать эффективность решений
• ⚡ Научиться выбирать оптимальные структуры данных для конкретных задач
• 🎯 Улучшить навыки оптимизации программ по времени и памяти
• 🔍 Подготовиться к техническим собеседованиям в ведущие IT-компании
• 🌟 Заложить фундамент для изучения более сложных алгоритмов и структур данных

Массивы и строки

Задача 1: Поиск пары с заданной суммой

Формулировка: Дан массив целых чисел и целевое значение. Необходимо найти пару чисел, сумма которых равна целевому значению.

Пример:

Массив: [2, 7, 11, 15]
Целевое значение: 9
Результат: [0, 1] (индексы пары чисел 2 и 7)

Решение с использованием хеш-таблицы:

function twoSum(nums, target) {
  const map = new Map()

  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i]

    if (map.has(complement)) {
      return [map.get(complement), i]
    }

    map.set(nums[i], i)
  }

  return [-1, -1] // Пара не найдена
}

Временная сложность: O(n)
Пространственная сложность: O(n)

Почему это эффективно?

Использование хеш-таблицы позволяет за O(1) проверять, есть ли в массиве число, дополняющее текущее до целевой суммы, что сокращает сложность с O(n²) до O(n).

Задача 2: Поиск самой длинной подстроки без повторяющихся символов

Формулировка: Дана строка, найти длину самой длинной подстроки без повторяющихся символов.

Пример:

Строка: "abcabcbb"
Результат: 3 (подстрока "abc")

Решение с использованием скользящего окна:

function lengthOfLongestSubstring(s) {
  const charSet = new Set()
  let maxLength = 0
  let left = 0

  for (let right = 0; right < s.length; right++) {
    // Если символ уже в окне, сжимаем окно слева
    while (charSet.has(s[right])) {
      charSet.delete(s[left])
      left++
    }

    // Добавляем текущий символ и обновляем максимальную длину
    charSet.add(s[right])
    maxLength = Math.max(maxLength, right - left + 1)
  }

  return maxLength
}

Временная сложность: O(n)
Пространственная сложность: O(min(n, m)), где m - размер алфавита

Почему это эффективно?

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

Связные списки

Задача 1: Определение цикла в связном списке

Формулировка: Определить, содержит ли односвязный список цикл.

Примеры:

Список: 1->2->3->4->2 (цикл)
Результат: true

Список: 1->2->3->4
Результат: false

Решение с использованием алгоритма "черепахи и зайца" (Флойда):

function hasCycle(head) {
  if (!head || !head.next) return false

  let slow = head // Черепаха (движется на 1 шаг)
  let fast = head // Заяц (движется на 2 шага)

  while (fast && fast.next) {
    slow = slow.next
    fast = fast.next.next

    // Если указатели встретились, в списке есть цикл
    if (slow === fast) {
      return true
    }
  }

  return false
}

Временная сложность: O(n)
Пространственная сложность: O(1)

Почему это эффективно?

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

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→

Задача 2: Разворот связного списка

Формулировка: Развернуть односвязный список.

Пример:

Исходный список: 1->2->3->4->5
Результат: 5->4->3->2->1

Итеративное решение:

function reverseList(head) {
  let prev = null
  let current = head

  while (current) {
    // Сохраняем следующий узел
    const next = current.next

    // Меняем указатель на предыдущий узел
    current.next = prev

    // Двигаем указатели вперед
    prev = current
    current = next
  }

  return prev // Новая голова списка
}

Временная сложность: O(n)
Пространственная сложность: O(1)

Почему это эффективно?

Решение требует всего трех указателей и одного прохода по списку, не используя дополнительную память для хранения узлов.

Стеки и очереди

Задача 1: Проверка сбалансированности скобок

Формулировка: Проверить, сбалансированы ли скобки в строке. Скобки могут быть трех типов: (), [], {}.

Примеры:

Строка: "{[]}"
Результат: true

Строка: "([)]"
Результат: false

Решение с использованием стека:

function isValid(s) {
  const stack = []
  const brackets = {
    ')': '(',
    ']': '[',
    '}': '{',
  }

  for (const char of s) {
    // Если открывающая скобка, помещаем в стек
    if (char === '(' || char === '[' || char === '{') {
      stack.push(char)
    }
    // Если закрывающая скобка
    else if (brackets[char]) {
      // Проверяем соответствие с последней открывающей скобкой
      if (stack.pop() !== brackets[char]) {
        return false
      }
    }
  }

  // Если стек пуст, все скобки сбалансированы
  return stack.length === 0
}

Временная сложность: O(n)
Пространственная сложность: O(n)

Почему это эффективно?

Стек идеально подходит для проверки баланса скобок, так как позволяет сопоставлять открывающие и закрывающие скобки в порядке "последний открытый - первый закрытый" (LIFO).

Задача 2: Реализация очереди с помощью двух стеков

Формулировка: Реализовать очередь, используя только два стека.

Решение:

class Queue {
  constructor() {
    this.stackNewest = [] // Для добавления элементов
    this.stackOldest = [] // Для извлечения элементов
  }

  // Добавление элемента в конец очереди
  enqueue(value) {
    this.stackNewest.push(value)
  }

  // Извлечение элемента из начала очереди
  dequeue() {
    // Если стек для извлечения пуст, переносим все элементы
    // из стека для добавления
    if (this.stackOldest.length === 0) {
      this.shiftStacks()
    }

    return this.stackOldest.pop()
  }

  // Перемещение всех элементов из stackNewest в stackOldest
  shiftStacks() {
    while (this.stackNewest.length > 0) {
      this.stackOldest.push(this.stackNewest.pop())
    }
  }

  // Получение размера очереди
  size() {
    return this.stackNewest.length + this.stackOldest.length
  }

  // Проверка, пуста ли очередь
  isEmpty() {
    return this.size() === 0
  }

  // Просмотр элемента в начале очереди
  peek() {
    if (this.stackOldest.length === 0) {
      this.shiftStacks()
    }

    return this.stackOldest[this.stackOldest.length - 1]
  }
}

Временная сложность:

• Enqueue: O(1) амортизированная
• Dequeue: O(1) амортизированная
• Peek: O(1) амортизированная

Пространственная сложность: O(n)

Почему это эффективно?

Хотя операция переноса элементов из одного стека в другой требует O(n) времени, она выполняется редко — только когда stackOldest пуст. Это дает амортизированную сложность O(1) для всех операций.

Деревья и графы

Задача 1: Инвертирование бинарного дерева

Формулировка: Инвертировать бинарное дерево (поменять местами левое и правое поддеревья для каждого узла).

Пример:

Исходное дерево:
     4
   /   \
  2     7
 / \   / \
1   3 6   9

Результат:
     4
   /   \
  7     2
 / \   / \
9   6 3   1

Рекурсивное решение:

function invertTree(root) {
  // Базовый случай: пустое дерево
  if (!root) return null

  // Меняем местами левое и правое поддеревья
  const temp = root.left
  root.left = root.right
  root.right = temp

  // Рекурсивно инвертируем поддеревья
  invertTree(root.left)
  invertTree(root.right)

  return root
}

Временная сложность: O(n)
Пространственная сложность: O(h), где h - высота дерева (в худшем случае O(n))

Почему это эффективно?

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

Задача 2: Поиск кратчайшего пути в графе (алгоритм Дейкстры)

Формулировка: Найти кратчайшие пути от заданной вершины до всех остальных вершин во взвешенном графе.

Решение с использованием приоритетной очереди:

function dijkstra(graph, start) {
  const distances = {}
  const previous = {}
  const pq = new PriorityQueue()

  // Инициализация
  for (const vertex in graph) {
    if (vertex === start) {
      distances[vertex] = 0
      pq.enqueue(vertex, 0)
    } else {
      distances[vertex] = Infinity
      pq.enqueue(vertex, Infinity)
    }
    previous[vertex] = null
  }

  // Основной алгоритм
  while (!pq.isEmpty()) {
    const current = pq.dequeue().element

    // Для каждого соседа текущей вершины
    for (const neighbor in graph[current]) {
      // Вычисляем новое расстояние
      const distance = distances[current] + graph[current][neighbor]

      // Если нашли более короткий путь
      if (distance < distances[neighbor]) {
        distances[neighbor] = distance
        previous[neighbor] = current
        pq.enqueue(neighbor, distance)
      }
    }
  }

  return { distances, previous }
}

// Реализация простой приоритетной очереди
class PriorityQueue {
  constructor() {
    this.values = []
  }

  enqueue(element, priority) {
    this.values.push({ element, priority })
    this.sort()
  }

  dequeue() {
    return this.values.shift()
  }

  sort() {
    this.values.sort((a, b) => a.priority - b.priority)
  }

  isEmpty() {
    return !this.values.length
  }
}

Временная сложность: O((V + E) log V), где V - количество вершин, E - количество рёбер
Пространственная сложность: O(V)

Почему это эффективно?

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

Хеш-таблицы

Задача 1: Подсчет частоты элементов

Формулировка: Подсчитать частоту каждого элемента в массиве.

Пример:

Массив: [1, 2, 3, 1, 2, 1, 3, 4]
Результат: {1: 3, 2: 2, 3: 2, 4: 1}

Решение:

function countFrequency(arr) {
  const frequencyMap = {}

  for (const element of arr) {
    if (frequencyMap[element]) {
      frequencyMap[element]++
    } else {
      frequencyMap[element] = 1
    }
  }

  return frequencyMap
}

Временная сложность: O(n)
Пространственная сложность: O(k), где k - количество уникальных элементов

Почему это эффективно?

Хеш-таблица обеспечивает доступ к элементам и их обновление за O(1), что делает общую сложность линейной.

Задача 2: Проверка анаграммы

Формулировка: Определить, являются ли две строки анаграммами (содержат одни и те же символы в разном порядке).

Пример:

Строка 1: "listen"
Строка 2: "silent"
Результат: true

Решение с использованием хеш-таблицы:

function areAnagrams(s1, s2) {
  // Если длины разные, это не анаграммы
  if (s1.length !== s2.length) return false

  const charCount = {}

  // Подсчитываем символы первой строки
  for (const char of s1) {
    charCount[char] = (charCount[char] || 0) + 1
  }

  // Вычитаем символы второй строки
  for (const char of s2) {
    // Если символа нет или его количество уже 0, это не анаграмма
    if (!charCount[char]) return false
    charCount[char]--
  }

  // Проверяем, что все счетчики обнулились
  return Object.values(charCount).every((count) => count === 0)
}

Временная сложность: O(n)
Пространственная сложность: O(k), где k - размер алфавита

Почему это эффективно?

Хеш-таблица позволяет за линейное время подсчитать и сравнить частоту символов, избегая необходимости сортировки строк (что потребовало бы O(n log n) времени).

Продвинутые структуры данных

Задача 1: Объединение интервалов

Формулировка: Дан набор интервалов, необходимо объединить перекрывающиеся интервалы.

Пример:

Интервалы: [[1,3], [2,6], [8,10], [15,18]]
Результат: [[1,6], [8,10], [15,18]]

Решение:

function mergeIntervals(intervals) {
  if (intervals.length <= 1) return intervals

  // Сортируем интервалы по начальной точке
  intervals.sort((a, b) => a[0] - b[0])

  const result = [intervals[0]]

  for (let i = 1; i < intervals.length; i++) {
    const currentInterval = intervals[i]
    const lastResultInterval = result[result.length - 1]

    // Если текущий интервал перекрывается с последним в результате
    if (currentInterval[0] <= lastResultInterval[1]) {
      // Обновляем конечную точку последнего интервала в результате
      lastResultInterval[1] = Math.max(
        lastResultInterval[1],
        currentInterval[1]
      )
    } else {
      // Добавляем интервал к результату
      result.push(currentInterval)
    }
  }

  return result
}

Временная сложность: O(n log n) из-за сортировки
Пространственная сложность: O(n)

Почему это эффективно?

Сортировка позволяет рассматривать интервалы в порядке возрастания начальных точек, что упрощает проверку перекрытия только с последним интервалом в результирующем массиве.

Задача 2: Реализация структуры данных "Система непересекающихся множеств" (Union-Find)

Формулировка: Реализовать структуру данных для эффективного выполнения операций объединения множеств и проверки, принадлежат ли два элемента одному множеству.

Решение с использованием сжатия путей и ранговой эвристики:

class UnionFind {
  constructor(size) {
    // Каждый элемент изначально является корнем своего множества
    this.parent = Array(size)
      .fill()
      .map((_, i) => i)
    // Ранг (примерная высота) каждого дерева
    this.rank = Array(size).fill(0)
  }

  // Найти корень множества, содержащего элемент x (с сжатием пути)
  find(x) {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x])
    }
    return this.parent[x]
  }

  // Объединить множества, содержащие элементы x и y
  union(x, y) {
    const rootX = this.find(x)
    const rootY = this.find(y)

    if (rootX === rootY) return

    // Присоединяем дерево меньшего ранга к дереву большего ранга
    if (this.rank[rootX] < this.rank[rootY]) {
      this.parent[rootX] = rootY
    } else if (this.rank[rootX] > this.rank[rootY]) {
      this.parent[rootY] = rootX
    } else {
      this.parent[rootY] = rootX
      this.rank[rootX]++
    }
  }

  // Проверка, принадлежат ли элементы x и y одному множеству
  connected(x, y) {
    return this.find(x) === this.find(y)
  }
}

Временная сложность:

• Find: O(α(n)), где α(n) - обратная функция Аккермана (практически константа)
• Union: O(α(n))
• Connected: O(α(n))

Пространственная сложность: O(n)

Почему это эффективно?

Сжатие путей (path compression) и ранговая эвристика (union by rank) делают операции find и union практически константными, что особенно важно для алгоритмов на графах, таких как Крускал.

Практические задачи и их решения

Задача 1: Реализация LRU-кеша (Least Recently Used)

Формулировка: Реализовать структуру данных LRU-кеш с операциями get и put в среднем за O(1).

Решение с использованием хеш-таблицы и двусвязного списка:

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity
    this.cache = new Map() // Хеш-таблица для быстрого доступа
    this.head = new Node(0, 0) // Фиктивная голова списка
    this.tail = new Node(0, 0) // Фиктивный хвост списка

    // Инициализация двусвязного списка
    this.head.next = this.tail
    this.tail.prev = this.head
  }

  // Получение значения по ключу
  get(key) {
    if (!this.cache.has(key)) return -1

    // Перемещаем узел в начало списка (он только что использовался)
    const node = this.cache.get(key)
    this.removeNode(node)
    this.addToFront(node)

    return node.value
  }

  // Добавление или обновление пары ключ-значение
  put(key, value) {
    // Если ключ уже существует, удаляем его из списка
    if (this.cache.has(key)) {
      this.removeNode(this.cache.get(key))
    }

    // Создаем новый узел и добавляем его в начало списка
    const newNode = new Node(key, value)
    this.addToFront(newNode)
    this.cache.set(key, newNode)

    // Если превышена емкость, удаляем наименее недавно использованный элемент
    if (this.cache.size > this.capacity) {
      const nodeToRemove = this.tail.prev
      this.removeNode(nodeToRemove)
      this.cache.delete(nodeToRemove.key)
    }
  }

  // Вспомогательный метод для удаления узла из списка
  removeNode(node) {
    node.prev.next = node.next
    node.next.prev = node.prev
  }

  // Вспомогательный метод для добавления узла в начало списка
  addToFront(node) {
    node.next = this.head.next
    node.prev = this.head
    this.head.next.prev = node
    this.head.next = node
  }
}

// Класс для узла двусвязного списка
class Node {
  constructor(key, value) {
    this.key = key
    this.value = value
    this.prev = null
    this.next = null
  }
}

Временная сложность:

• Get: O(1)
• Put: O(1)

Пространственная сложность: O(capacity)

Почему это эффективно?

Комбинация хеш-таблицы и двусвязного списка позволяет получать значения и обновлять порядок использования за O(1), а также эффективно удалять наименее недавно использованные элементы.

Задача 2: Реализация префиксного дерева (Trie)

Формулировка: Реализовать префиксное дерево (Trie) для эффективного поиска строк и префиксов.

Решение:

class TrieNode {
  constructor() {
    this.children = {}
    this.isEndOfWord = false
  }
}

class Trie {
  constructor() {
    this.root = new TrieNode()
  }

  // Вставка слова в дерево
  insert(word) {
    let current = this.root

    for (const char of word) {
      if (!current.children[char]) {
        current.children[char] = new TrieNode()
      }
      current = current.children[char]
    }

    current.isEndOfWord = true
  }

  // Поиск слова в дереве
  search(word) {
    let current = this.root

    for (const char of word) {
      if (!current.children[char]) {
        return false
      }
      current = current.children[char]
    }

    return current.isEndOfWord
  }

  // Проверка, существует ли слово с данным префиксом
  startsWith(prefix) {
    let current = this.root

    for (const char of prefix) {
      if (!current.children[char]) {
        return false
      }
      current = current.children[char]
    }

    return true
  }
}

Временная сложность:

• Insert: O(m), где m - длина слова
• Search: O(m)
• StartsWith: O(m)

Пространственная сложность: O(n × m), где n - количество слов, m - средняя длина слова

Почему это эффективно?

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

Дополнительные задачи на структуры данных

Задача 3: Реализация структуры данных "MinStack"

Формулировка: Реализовать стек, который поддерживает операции push, pop, top и getMin (получение минимального элемента) со сложностью O(1).

Решение с использованием дополнительного стека:

class MinStack {
  constructor() {
    this.stack = [] // Основной стек
    this.minStack = [] // Стек для отслеживания минимальных элементов
  }

  push(val) {
    this.stack.push(val)

    // Если minStack пуст или новое значение <= текущему минимуму
    if (
      this.minStack.length === 0 ||
      val <= this.minStack[this.minStack.length - 1]
    ) {
      this.minStack.push(val)
    }
  }

  pop() {
    // Если удаляемый элемент равен текущему минимуму,
    // также удаляем его из minStack
    if (
      this.stack[this.stack.length - 1] ===
      this.minStack[this.minStack.length - 1]
    ) {
      this.minStack.pop()
    }

    return this.stack.pop()
  }

  top() {
    return this.stack[this.stack.length - 1]
  }

  getMin() {
    return this.minStack[this.minStack.length - 1]
  }
}

Временная сложность:

• Push: O(1)
• Pop: O(1)
• Top: O(1)
• GetMin: O(1)

Пространственная сложность: O(n)

Почему это эффективно?

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

Задача 4: Реализация кеша с временем жизни (TTL)

Формулировка: Реализовать кеш с функциями get и put, где каждый ключ имеет время жизни (Time To Live), по истечении которого ключ автоматически удаляется.

Решение с использованием хеш-таблицы и приоритетной очереди:

class TTLCache {
  constructor() {
    this.cache = new Map() // Хранение данных
    this.expiryQueue = new MinPriorityQueue() // Очередь с приоритетом по времени истечения
  }

  // Получение значения по ключу
  get(key, currentTime) {
    // Удаляем просроченные записи
    this.removeExpired(currentTime)

    if (!this.cache.has(key)) return null

    const { value, expiry } = this.cache.get(key)

    // Проверяем, не истек ли срок ключа
    if (expiry <= currentTime) {
      this.cache.delete(key)
      return null
    }

    return value
  }

  // Добавление ключа со значением и временем жизни
  put(key, value, ttl, currentTime) {
    // Удаляем просроченные записи
    this.removeExpired(currentTime)

    // Вычисляем время истечения срока
    const expiry = currentTime + ttl

    // Сохраняем данные в кеше
    this.cache.set(key, { value, expiry })

    // Добавляем запись в очередь истечения сроков
    this.expiryQueue.enqueue({ key, expiry }, expiry)
  }

  // Удаление просроченных записей
  removeExpired(currentTime) {
    while (
      !this.expiryQueue.isEmpty() &&
      this.expiryQueue.front().priority <= currentTime
    ) {
      const { key } = this.expiryQueue.dequeue().element

      // Проверяем, что запись всё еще в кеше и срок действительно истек
      // (могли быть перезаписаны с новым сроком)
      if (this.cache.has(key) && this.cache.get(key).expiry <= currentTime) {
        this.cache.delete(key)
      }
    }
  }
}

// Пример реализации простой приоритетной очереди
class MinPriorityQueue {
  constructor() {
    this.elements = []
  }

  enqueue(element, priority) {
    this.elements.push({ element, priority })
    this.elements.sort((a, b) => a.priority - b.priority)
  }

  dequeue() {
    return this.elements.shift()
  }

  front() {
    return this.elements[0]
  }

  isEmpty() {
    return this.elements.length === 0
  }
}

Временная сложность:

• Get: O(k), где k - количество истекших записей на момент вызова
• Put: O(k + log n) из-за сортировки в приоритетной очереди

Пространственная сложность: O(n)

Почему это эффективно?

Комбинация хеш-таблицы и приоритетной очереди позволяет эффективно хранить данные и отслеживать их срок действия, удаляя просроченные записи при необходимости.

Задача 5: Поиск максимальной области в гистограмме

Формулировка: Дан массив положительных чисел, представляющий высоты столбцов гистограммы. Найти площадь самого большого прямоугольника в гистограмме.

Пример:

Высоты: [2, 1, 5, 6, 2, 3]
Результат: 10 (прямоугольник 5 × 2)

Решение с использованием стека:

function largestRectangleArea(heights) {
  const stack = [] // Стек для хранения индексов возрастающих высот
  let maxArea = 0
  let i = 0

  while (i < heights.length) {
    // Если стек пуст или высота текущего столбца больше или равна высоте столбца на вершине стека
    if (stack.length === 0 || heights[i] >= heights[stack[stack.length - 1]]) {
      stack.push(i++)
    }
    // Если высота текущего столбца меньше, вычисляем площадь с вершиной стека как наименьшей высотой
    else {
      const topIndex = stack.pop()

      // Вычисляем ширину: если стек пуст, то от начала до i, иначе от предыдущего индекса в стеке до i
      const width = stack.length === 0 ? i : i - stack[stack.length - 1] - 1

      // Вычисляем площадь и обновляем максимум
      const area = heights[topIndex] * width
      maxArea = Math.max(maxArea, area)
    }
  }

  // Обрабатываем оставшиеся элементы в стеке
  while (stack.length > 0) {
    const topIndex = stack.pop()
    const width = stack.length === 0 ? i : i - stack[stack.length - 1] - 1
    const area = heights[topIndex] * width
    maxArea = Math.max(maxArea, area)
  }

  return maxArea
}

Временная сложность: O(n)
Пространственная сложность: O(n)

Почему это эффективно?

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

Алгоритмические шаблоны на основе структур данных

1. Скользящее окно

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

Пример задачи: Максимальная сумма подмассива длины k

Формулировка: Найти максимальную сумму подмассива фиксированной длины k.

function maxSubarraySum(arr, k) {
  if (arr.length < k) return null

  // Вычисляем сумму первых k элементов
  let maxSum = 0
  for (let i = 0; i < k; i++) {
    maxSum += arr[i]
  }

  // Инициализируем текущую сумму
  let currentSum = maxSum

  // Сдвигаем окно и обновляем суммы
  for (let i = k; i < arr.length; i++) {
    // Добавляем новый элемент и удаляем первый элемент предыдущего окна
    currentSum = currentSum + arr[i] - arr[i - k]
    maxSum = Math.max(maxSum, currentSum)
  }

  return maxSum
}

Временная сложность: O(n)
Пространственная сложность: O(1)

2. Два указателя

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

Пример задачи: Удаление дубликатов из отсортированного массива

Формулировка: Удалить дубликаты из отсортированного массива, вернуть новую длину.

function removeDuplicates(nums) {
  if (nums.length === 0) return 0

  // Указатель на текущую позицию для уникальных элементов
  let i = 0

  // Второй указатель перебирает массив
  for (let j = 1; j < nums.length; j++) {
    // Если элементы отличаются, сохраняем новый уникальный элемент
    if (nums[j] !== nums[i]) {
      i++
      nums[i] = nums[j]
    }
  }

  return i + 1 // Новая длина массива
}

Временная сложность: O(n)
Пространственная сложность: O(1)

3. Быстрая и медленная ссылки (Fast and Slow pointers)

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

Пример задачи: Нахождение середины связного списка

Формулировка: Найти средний узел связного списка за один проход.

function middleNode(head) {
  // Если список пуст или содержит один элемент
  if (!head || !head.next) return head

  let slow = head // Медленный указатель (1 шаг)
  let fast = head // Быстрый указатель (2 шага)

  // Пока быстрый указатель может двигаться
  while (fast && fast.next) {
    slow = slow.next
    fast = fast.next.next
  }

  return slow // Медленный указатель будет на середине
}

Временная сложность: O(n)
Пространственная сложность: O(1)

4. Префиксная сумма

Этот шаблон предварительно вычисляет суммы подмассивов, что позволяет эффективно вычислять сумму любого диапазона. Полезен для задач, требующих многократного вычисления сумм подмассивов.

Пример задачи: Нахождение подмассива с заданной суммой

Формулировка: Определить, существует ли непрерывный подмассив с заданной суммой.

function hasSubarraySum(nums, target) {
  const prefixSums = new Set()
  let sum = 0

  // Добавляем 0 для случая, когда подмассив начинается с начала
  prefixSums.add(0)

  for (const num of nums) {
    sum += num

    // Если (sum - target) есть в множестве, значит существует подмассив с суммой target
    if (prefixSums.has(sum - target)) {
      return true
    }

    prefixSums.add(sum)
  }

  return false
}

Временная сложность: O(n)
Пространственная сложность: O(n)

5. Монотонный стек/очередь

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

Пример задачи: Нахождение следующего большего элемента

Формулировка: Для каждого элемента массива найти следующий больший элемент (элемент, который находится правее и имеет большее значение).

function nextGreaterElement(nums) {
  const n = nums.length
  const result = Array(n).fill(-1) // По умолчанию -1 (нет большего элемента)
  const stack = [] // Стек для хранения индексов

  for (let i = 0; i < n; i++) {
    // Пока стек не пуст и текущий элемент больше элемента на вершине стека
    while (stack.length > 0 && nums[i] > nums[stack[stack.length - 1]]) {
      const index = stack.pop()
      result[index] = nums[i] // Нашли следующий больший элемент
    }

    stack.push(i)
  }

  return result
}

Временная сложность: O(n)
Пространственная сложность: O(n)

Применение структур данных в реальных задачах

Web-разработка:

• Кеширование: LRU-кеш и TTL-кеш для ускорения работы веб-приложений
• Маршрутизация: Префиксные деревья и графы для обработки URL и маршрутизации запросов
• Сессии пользователей: Хеш-таблицы для хранения информации о сессиях
• Очереди заданий: Очереди с приоритетом для планирования задач

Базы данных:

• Индексы: B-деревья и хеш-таблицы для быстрого поиска данных
• Транзакции: Очереди и журналы для управления транзакциями
• Кеширование запросов: Различные кеш-структуры для часто запрашиваемых данных
• Распределенное хранение: Системы непересекающихся множеств и хеш-кольца

Машинное обучение:

• Kd-деревья: Для ускорения поиска ближайших соседей
• Решающие деревья: Древовидные структуры для классификации и регрессии
• Графовые модели: Графы для представления сложных взаимосвязей
• Быстрые вычисления: Оптимизированные структуры данных для ускорения вычислений

Операционные системы:

• Планирование процессов: Различные очереди и кучи для планирования
• Файловые системы: B-деревья, индексные структуры для организации данных
• Управление памятью: Списки свободных блоков, битовые карты
• Сетевые стеки: Очереди и буферы для обработки пакетов

Рекомендации по изучению и решению задач

1. Поэтапное изучение структур данных:

• Начните с базовых структур: массивы, строки, связные списки
• Переходите к более сложным: стеки, очереди, деревья
• Изучайте продвинутые: графы, хеш-таблицы, кучи
• Осваивайте специализированные: префиксные деревья, системы непересекающихся множеств

2. Эффективный подход к решению задач:

• Сначала анализируйте задачу и определяйте подходящие структуры данных
• Рассматривайте компромиссы между временем и пространством
• Начинайте с прямолинейного решения, затем оптимизируйте
• Работайте над пониманием шаблонов и алгоритмических приемов

3. Практические советы:

• Решайте задачи регулярно, начиная с простых
• Реализуйте структуры данных с нуля для лучшего понимания
• Анализируйте сложность своих решений
• Участвуйте в соревнованиях по программированию для применения знаний

Заключение

Эффективное использование структур данных является фундаментальным навыком для любого разработчика. Выбор правильной структуры данных может значительно повлиять на производительность программы и элегантность решения.

Ключевые выводы:

• 🧩 Каждая структура данных имеет свои сильные и слабые стороны, подходящие для определенных типов задач
• 🔎 Важно не только знать, как реализовать структуру данных, но и понимать, когда ее использовать
• ⚖️ Всегда учитывайте компромиссы между временем выполнения и использованием памяти
• 🧪 Регулярная практика решения задач — лучший способ освоить структуры данных
• 🚀 Многие алгоритмические шаблоны основаны на эффективном использовании структур данных

Владение различными структурами данных и понимание их применимости — это навык, который остается актуальным независимо от языка программирования или технологического стека. Это инвестиция в фундаментальные знания, которая будет приносить дивиденды на протяжении всей карьеры разработчика. 🌟