Монотонные стек и очередь. Поиск следующего большего/меньшего, sliding window maximum.
Стек/очередь с поддержанием монотонности (возрастание/убывание). Для поиска следующего большего/меньшего, sliding window maximum.
Monotonic Stack/Queue — это структура данных, которая поддерживает элементы в монотонном порядке (возрастающем или убывающем). Это позволяет эффективно находить следующий больший/меньший элемент и решать задачи на диапазоны.
| Тип | Порядок в стеке | Для чего |
|---|---|---|
| Убывающий стек | Большие → Меньшие | Next Greater Element |
| Возрастающий стек | Меньшие → Большие | Next Smaller Element, Largest Rectangle |
| Monotonic Queue | Убывающий/Возрастающий | Sliding Window Maximum |
Убывающий стек для [5, 3, 1, 4, 2]:
i=0: stack = [5] (5)
i=1: stack = [5, 3] (5, 3)
i=2: stack = [5, 3, 1] (5, 3, 1)
i=3: 4 > 1, pop 1 → 4 > 3, pop 3 → stack = [5, 4]
i=4: stack = [5, 4, 2] (5, 4, 2)
Next Greater для 1 = 4, для 3 = 4, для 5 = -1
| Задача | Monotonic Stack | Brute Force | Segment Tree |
|---|---|---|---|
| Next Greater | ✅ O(n) | ❌ O(n²) | ⚠️ O(n log n) |
| Sliding Window Max | ✅ O(n) | ❌ O(n × k) | ⚠️ O(n log n) |
| Largest Rectangle | ✅ O(n) | ❌ O(n²) | ❌ Не применимо |
| Простота | ✅ Простой | ✅ Простой | ⚠️ Сложный |
Вывод: Monotonic Stack даёт оптимальное O(n) решение для задач на следующий больший/меньший элемент.
def nextGreaterElement(nums):
stack = [] # Хранит индексы в порядке убывания значений
result = [-1] * len(nums)
for i, num in enumerate(nums):
while stack and nums[stack[-1]] < num:
idx = stack.pop()
result[idx] = num
stack.append(i)
return resultfrom collections import deque
def maxSlidingWindow(nums, k):
dq = deque() # Хранит индексы в порядке убывания значений
result = []
for i in range(len(nums)):
# Удаляем вышедшие из окна
if dq and dq[0] == i - k:
dq.popleft()
# Удаляем меньшие элементы
while dq and nums[dq[-1]] < nums[i]:
dq.pop()
dq.append(i)
if i >= k - 1:
result.append(nums[dq[0]])
return resultУсловие:
Даны два массива nums1 и nums2, где nums1 является подмножеством nums2.
Для каждого элемента в nums1 найдите следующий больший элемент в nums2 (справа от него). Если такого нет, верните -1.
Примеры:
Ввод: nums1 = [4,1,2], nums2 = [1,3,4,2]
Вывод: [-1,3,-1]
Объяснение:
4: нет следующего большего → -1
1: следующий больший 3 → 3
2: нет следующего большего → -1
Ввод: nums1 = [2,4], nums2 = [1,2,3,4]
Вывод: [3,-1]
Ограничения:
💡 Подсказка: Используйте монотонный убывающий стек для nums2. Храните mapping: число → следующий больший.
nums = [5, 3, 1, 4, 2]
result = [-1, -1, -1, -1, -1] # Изначально
Шаг 1: i=0, num=5
stack = [0] # Индекс 5
Шаг 2: i=1, num=3
3 < 5, push
stack = [0, 1]
Шаг 3: i=2, num=1
1 < 3, push
stack = [0, 1, 2]
Шаг 4: i=3, num=4
4 > 1, pop 2, result[2] = 4
4 > 3, pop 1, result[1] = 4
4 < 5, push
stack = [0, 3]
Шаг 5: i=4, num=2
2 < 4, push
stack = [0, 3, 4]
Результат: [-1, 4, 4, -1, -1]
Решение:
def nextGreaterElement(nums1, nums2):
next_greater = {}
stack = []
for num in nums2:
while stack and stack[-1] < num:
next_greater[stack.pop()] = num
stack.append(num)
return [next_greater.get(num, -1) for num in nums1]Объяснение:
Сложность:
Условие:
Дан циклический массив nums. Верните следующий больший элемент для каждого элемента.
Циклический: после последнего элемента снова идёт первый. Если нет следующего большего, верните -1.
Примеры:
Ввод: nums = [1,2,1]
Вывод: [2,-1,2]
Объяснение:
1 (index 0): следующий больший 2 → 2
2: нет следующего большего → -1
1 (index 2): следующий больший 2 (циклически) → 2
Ввод: nums = [1,2,3,4,3]
Вывод: [2,3,4,-1,4]
Ограничения:
💡 Подсказка: Два прохода по массиву (2 × n итераций). Индекс в массиве: i % n.
Решение:
def nextGreaterElements(nums):
n = len(nums)
result = [-1] * n
stack = []
# Два прохода для цикличности
for i in range(2 * n):
num = nums[i % n]
while stack and nums[stack[-1]] < num:
result[stack.pop()] = num
if i < n:
stack.append(i)
return resultОбъяснение:
Сложность:
Условие:
Дан массив temperatures, где temperatures[i] — температура в i-й день.
Верните массив answer, где answer[i] — количество дней, которое нужно ждать до более тёплого дня. Если теплее не будет, answer[i] = 0.
Примеры:
Ввод: temperatures = [73,74,75,71,69,72,76,73]
Вывод: [1,1,4,2,1,1,0,0]
Ввод: temperatures = [30,40,50,60]
Вывод: [1,1,1,0]
Ввод: temperatures = [30,60,90]
Вывод: [1,1,0]
Ограничения:
💡 Подсказка: Используйте монотонный убывающий стек индексов. Когда температура растёт — вычисляем разницу индексов.
Решение:
def dailyTemperatures(temperatures):
result = [0] * len(temperatures)
stack = [] # Индексы дней в порядке убывания температур
for i, temp in enumerate(temperatures):
while stack and temperatures[stack[-1]] < temp:
prev_i = stack.pop()
result[prev_i] = i - prev_i # Количество дней
stack.append(i)
return resultОбъяснение:
Сложность:
Условие:
Дан массив heights, где heights[i] — высота столбца в гистограмме. Найдите площадь наибольшего прямоугольника.
Примеры:
Ввод: heights = [2,1,5,6,2,3]
Вывод: 10
Объяснение: Прямоугольник 5×2 (столбцы с высотой 5 и 6)
Ввод: heights = [2,4]
Вывод: 4
Ограничения:
💡 Подсказка: Используйте возрастающий стек. Добавьте 0 в конец как sentinel для принудительного выталкивания.
heights = [2, 1, 5, 6, 2, 3]
stack = [] # Индексы в порядке возрастания высот
max_area = 0
i=0, h=2: stack = [0]
i=1, h=1: 1 < 2, pop 0
height = 2, width = 1, area = 2
stack = [1]
i=2, h=5: stack = [1, 2]
i=3, h=6: stack = [1, 2, 3]
i=4, h=2: 2 < 6, pop 3, area = 6*1 = 6
2 < 5, pop 2, area = 5*2 = 10
stack = [1, 4]
i=5, h=3: stack = [1, 4, 5]
Добавляем sentinel 0 в конец для очистки стека
max_area = 10
Решение:
def largestRectangleArea(heights):
stack = [] # Индексы в порядке возрастания высот
max_area = 0
heights.append(0) # Sentinel
for i, h in enumerate(heights):
while stack and heights[stack[-1]] > h:
height = heights[stack.pop()]
# Ширина: от предыдущего в стеке до текущего
width = i if not stack else i - stack[-1] - 1
max_area = max(max_area, height * width)
stack.append(i)
heights.pop() # Восстанавливаем (опционально)
return max_areaОбъяснение:
Сложность:
Условие:
Дана бинарная матрица matrix (символы '0' и '1'). Найдите площадь наибольшего прямоугольника, состоящего только из '1'.
Примеры:
Ввод: matrix = [
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]
]
Вывод: 6
Ввод: matrix = [["0"]]
Вывод: 0
Ввод: matrix = [["1"]]
Вывод: 1
Ограничения:
💡 Подсказка: Для каждой строки вычисляйте heights (кумулятивная высота единиц). Применяйте Largest Rectangle к heights.
Решение:
def maximalRectangle(matrix):
if not matrix:
return 0
n = len(matrix[0])
heights = [0] * (n + 1) # +1 для sentinel
max_area = 0
for row in matrix:
# Обновляем heights
for i in range(n):
heights[i] = heights[i] + 1 if row[i] == '1' else 0
# Largest Rectangle для текущих heights
stack = []
for i, h in enumerate(heights):
while stack and heights[stack[-1]] > h:
height = heights[stack.pop()]
width = i if not stack else i - stack[-1] - 1
max_area = max(max_area, height * width)
stack.append(i)
return max_areaОбъяснение:
Сложность:
Условие:
Дан массив nums и размер окна k. Окно скользит слева направо. Верните массив максимумов для каждого положения окна.
Примеры:
Ввод: nums = [1,3,-1,-3,5,3,6,7], k = 3
Вывод: [3,3,5,5,6,7]
Объяснение:
[1,3,-1] → 3
[3,-1,-3] → 3
[-1,-3,5] → 5
[-3,5,3] → 5
[5,3,6] → 6
[3,6,7] → 7
Ввод: nums = [1], k = 1
Вывод: [1]
Ограничения:
💡 Подсказка: Используйте монотонную очередь (deque). Храните индексы в порядке убывания значений. dq[0] — максимум.
Решение:
from collections import deque
def maxSlidingWindow(nums, k):
dq = deque() # Индексы в порядке убывания значений
result = []
for i in range(len(nums)):
# Удаляем вышедшие из окна
if dq and dq[0] == i - k:
dq.popleft()
# Удаляем меньшие элементы (монотонность)
while dq and nums[dq[-1]] < nums[i]:
dq.pop()
dq.append(i)
# Добавляем максимум окна
if i >= k - 1:
result.append(nums[dq[0]])
return resultОбъяснение:
Сложность:
Условие:
Дан массив nums (может содержать отрицательные числа) и целое k. Верните длину кратчайшего подмассива с суммой >= k. Если такого нет, верните -1.
Примеры:
Ввод: nums = [1], k = 1
Вывод: 1
Ввод: nums = [1,2], k = 4
Вывод: -1
Ввод: nums = [2,-1,2], k = 3
Вывод: 3
Ограничения:
💡 Подсказка: Используйте префиксные суммы и монотонную очередь. Если prefix[dq[-1]] >= current, удаляем — current лучше.
Решение:
from collections import deque
def shortestSubarray(nums, k):
n = len(nums)
# Префиксные суммы
prefix = [0] * (n + 1)
for i in range(n):
prefix[i + 1] = prefix[i] + nums[i]
dq = deque()
min_len = float('inf')
for i, p in enumerate(prefix):
# Проверяем условие суммы
while dq and p - prefix[dq[0]] >= k:
min_len = min(min_len, i - dq.popleft())
# Поддерживаем монотонность
while dq and prefix[dq[-1]] >= p:
dq.pop()
dq.append(i)
return min_len if min_len != float('inf') else -1Объяснение:
Сложность:
Условие:
Дана строка num, представляющая неотрицательное целое число, и целое k. Удалите k цифр так, чтобы получить наименьшее возможное число.
Верните результат как строку (без ведущих нулей).
Примеры:
Ввод: num = "1432219", k = 3
Вывод: "1219"
Объяснение: Удалить 4, 3, 2 → "1219"
Ввод: num = "10200", k = 1
Вывод: "200"
Ввод: num = "10", k = 2
Вывод: "0"
Ограничения:
💡 Подсказка: Монотонный стек: пока k > 0 и stack[-1] > digit, удаляем. Сохраняем наименьшие цифры в старших разрядах.
Решение:
def removeKdigits(num, k):
stack = []
for digit in num:
while k > 0 and stack and stack[-1] > digit:
stack.pop()
k -= 1
stack.append(digit)
# Если остались удаления — удаляем с конца
while k > 0:
stack.pop()
k -= 1
result = ''.join(stack).lstrip('0')
return result if result else '0'Объяснение:
Сложность:
Условие:
Даны два массива nums1 и nums2 длины m и n. Создайте максимальное число длины k из цифр обоих массивов, сохраняя относительный порядок цифр из каждого массива.
Примеры:
Ввод: nums1 = [3,4,6,5], nums2 = [9,1,2,5,8,3], k = 5
Вывод: [9,8,6,5,3]
Ввод: nums1 = [6,7], nums2 = [6,0,4], k = 5
Вывод: [6,7,6,0,4]
Ввод: nums1 = [3,9], nums2 = [8,9], k = 3
Вывод: [9,8,9]
Ограничения:
💡 Подсказка: Переберите i цифр из nums1 и k-i из nums2. Для каждого массива создайте максимальную подпоследовательность (монотонный стек). Затем слейте.
Решение:
def maxNumber(nums1, nums2, k):
def max_subsequence(nums, k):
"""Максимальная подпоследовательность длины k"""
stack = []
drop = len(nums) - k
for num in nums:
while drop > 0 and stack and stack[-1] < num:
stack.pop()
drop -= 1
stack.append(num)
return stack[:k]
def merge(a, b):
"""Слияние двух массивов в максимальный"""
result = []
while a or b:
# Сравниваем лексикографически
if a > b:
result.append(a.pop(0))
else:
result.append(b.pop(0))
return result
max_result = []
# Перебираем количество цифр из nums1
for i in range(max(0, k - len(nums2)), min(k, len(nums1)) + 1):
merged = merge(max_subsequence(nums1, i),
max_subsequence(nums2, k - i))
max_result = max(max_result, merged)
return max_resultОбъяснение:
Сложность:
| Задача | Тип | Ключевая идея |
|---|---|---|
| Next Greater I | Stack | Убывающий стек + словарь |
| Next Greater II | Stack | Два прохода (2n) |
| Daily Temperatures | Stack | Индексы в стеке |
| Largest Rectangle | Stack | Возрастающий стек + sentinel |
| Maximal Rectangle | Stack | Heights для каждой строки |
| Sliding Window Max | Queue | deque с индексами |
| Shortest Subarray K | Queue | Префиксные суммы + монотонность |
| Remove K Digits | Stack | Удалить, пока prev > curr |
| Create Maximum | Stack | max_subsequence + merge |
Проблема: Путают возрастающий и убывающий стек.
# ❌ Неправильно для Next Greater
while stack and stack[-1] < num: # Возрастающий!
stack.pop()
# ✅ Правильно — убывающий стек
while stack and stack[-1] < num: # Выталкиваем меньшие
idx = stack.pop()
result[idx] = numПочему это неправильно: Next Greater требует убывающего стека.
Проблема: Остаток стека не обрабатывается.
# ❌ Неправильно
for i, h in enumerate(heights):
while stack and heights[stack[-1]] > h:
# Остаток стека не обработан!
# ✅ Правильно
heights.append(0) # Sentinel для очистки стека
for i, h in enumerate(heights):
while stack and heights[stack[-1]] > h:
# Все элементы будут обработаны
heights.pop() # ВосстанавливаемПочему это неправильно: Без sentinel некоторые элементы останутся в стеке.
Проблема: Неверно вычисляют ширину.
# ❌ Неправильно
width = i - stack[-1] # Забыли -1!
# ✅ Правильно
height = heights[stack.pop()]
width = i if not stack else i - stack[-1] - 1
area = height * widthПочему это неправильно: Ширина = правая граница - левая граница - 1.
Проблема: Стек не поддерживает popleft.
# ❌ Неправильно
stack = []
stack.pop(0) # O(n) вместо O(1)!
# ✅ Правильно
from collections import deque
dq = deque()
dq.popleft() # O(1)Почему это неправильно: Стек не поддерживает эффективное удаление с начала.
Проблема: Не проверяют пустую очередь.
# ❌ Неправильно
while dq and p - prefix[dq[0]] >= k:
# Может быть IndexError для пустой dq
# ✅ Правильно
while dq and p - prefix[dq[0]] >= k:
min_len = min(min_len, i - dq.popleft())Почему это неправильно: deque может быть пустой.
Условие: Дан массив температур. Для каждого дня найдите, сколько дней нужно ждать до более тёплой температуры.
Пример:
Ввод: temperatures = [73,74,75,71,69,72,76,73]
Вывод: [1,1,0,0,1,0,0]
Объяснение:
73→74 (1 день), 74→75 (1 день), 75→нет (0), 71→72 (1 день), ...
def dailyTemperatures(temperatures):
n = len(temperatures)
result = [0] * n
stack = [] # Индексы дней с убывающими температурами
for i, temp in enumerate(temperatures):
# Пока текущая температура больше температуры на вершине
while stack and temperatures[stack[-1]] < temp:
prev_i = stack.pop()
result[prev_i] = i - prev_i # Разница дней
stack.append(i)
return result
# Пример:
# temperatures = [73,74,75,71,69,72,76,73]
# i=0: stack=[0]
# i=1: 74>73, pop 0, result[0]=1, stack=[1]
# i=2: 75>74, pop 1, result[1]=1, stack=[2]
# i=3: 71<75, stack=[2,3]
# i=4: 69<71, stack=[2,3,4]
# i=5: 72>69, pop 4, result[4]=1, 72>71, pop 3, result[3]=1
# i=6: 76>75, pop 2, result[2]=3, stack=[6]
# i=7: 73<76, stack=[6,7]
# return [1,1,3,1,1,0,0,0]Объяснение:
Сложность:
Monotonic Stack/Queue для задач на:
Типы:
Вопросы ещё не добавлены
Вопросы для этой подтемы ещё не добавлены.