Monotonic Stack/Queue

Стек/очередь с поддержанием монотонности (возрастание/убывание). Для поиска следующего большего/меньшего, sliding window maximum.

#1. Суть паттерна

Monotonic Stack/Queue — это структура данных, которая поддерживает элементы в монотонном порядке (возрастающем или убывающем). Это позволяет эффективно находить следующий больший/меньший элемент и решать задачи на диапазоны.

#Когда применять

✅ Next Greater/Smaller Element — поиск следующего большего/меньшего элемента
✅ Previous Greater/Smaller — поиск предыдущего большего/меньшего
✅ Sliding Window Maximum — максимум в скользящем окне
✅ Largest Rectangle in Histogram — площадь в гистограмме
✅ Remove K Digits — удаление цифр для минимального числа

#Предусловия

Порядок важен — нужно сохранить относительный порядок элементов
Монотонность — ищем элементы по условию сравнения (>, <)
Однопроходность — обработка за один проход по массиву

#Типы

Тип	Порядок в стеке	Для чего
Убывающий стек	Большие → Меньшие	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) решение для задач на следующий больший/меньший элемент.

#2. Шаблон

#Monotonic Stack (Next Greater Element)

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 result

#Monotonic Queue (Sliding Window Maximum)

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

#3. Разбор задач

#Задача 1: Next Greater Element I (LeetCode 496) 🟩 Easy

Ссылка: https://leetcode.com/problems/next-greater-element-i/

Условие: Даны два массива 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]

Ограничения:

1 <= nums1.length <= nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 10⁴

💡 Подсказка: Используйте монотонный убывающий стек для 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]

Объяснение:

Проходим по nums2, поддерживаем убывающий стек
Когда встречаем элемент больше вершины — это Next Greater для неё
Сохраняем в словарь, затем используем для nums1

Сложность:

Время: O(n + m), где n = len(nums2), m = len(nums1)
Память: O(n) для словаря

#Задача 2: Next Greater Element II (LeetCode 503) 🟦 Medium

Ссылка: https://leetcode.com/problems/next-greater-element-ii/

Условие: Дан циклический массив 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]

Ограничения:

1 <= nums.length <= 10⁴
-10⁹ <= nums[i] <= 10⁹

💡 Подсказка: Два прохода по массиву (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

Объяснение:

Цикл for i in range(2 * n) эмулирует циклический массив
Индекс в массиве: i % n
Добавляем в стек только в первом проходе (i < n)

Сложность:

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

#Задача 3: Daily Temperatures (LeetCode 739) 🟦 Medium

Ссылка: https://leetcode.com/problems/daily-temperatures/

Условие: Дан массив 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]

Ограничения:

1 <= temperatures.length <= 10⁵
30 <= temperatures[i] <= 100

💡 Подсказка: Используйте монотонный убывающий стек индексов. Когда температура растёт — вычисляем разницу индексов.

Решение:

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

Объяснение:

stack хранит индексы дней с убывающими температурами
Когда temperatures[i] > temperatures[stack[-1]] — нашли тёплый день
result[prev_i] = i - prev_i — разница в днях

Сложность:

Время: O(n) — каждый элемент добавляется и удаляется один раз
Память: O(n)

#Задача 4: Largest Rectangle in Histogram (LeetCode 84) 🔴 Hard

Ссылка: https://leetcode.com/problems/largest-rectangle-in-histogram/

Условие: Дан массив heights, где heights[i] — высота столбца в гистограмме. Найдите площадь наибольшего прямоугольника.

Примеры:

Ввод: heights = [2,1,5,6,2,3]
Вывод: 10
Объяснение: Прямоугольник 5×2 (столбцы с высотой 5 и 6)

Ввод: heights = [2,4]
Вывод: 4

Ограничения:

1 <= heights.length <= 10⁵
0 <= heights[i] <= 10⁴

💡 Подсказка: Используйте возрастающий стек. Добавьте 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

Объяснение:

stack хранит индексы в порядке возрастания высот
Когда heights[i] < heights[stack[-1]] — вычисляем площадь для stack[-1]
sentinel (0) гарантирует выталкивание всех элементов
width = i - stack[-1] - 1 (расстояние между границами)

Сложность:

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

#Задача 5: Maximal Rectangle (LeetCode 85) 🔴 Hard

Ссылка: https://leetcode.com/problems/maximal-rectangle/

Условие: Дана бинарная матрица 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

Ограничения:

rows == matrix.length
cols == matrix[i].length
1 <= rows, cols <= 200
matrix[i][j] — '0' или '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

Объяснение:

heights[i] — кумулятивная высота единиц в колонке i
Для каждой строки применяем алгоритм Largest Rectangle
max_area по всем строкам — ответ

Сложность:

Время: O(m × n), где m = rows, n = cols
Память: O(n)

#Задача 6: Sliding Window Maximum (LeetCode 239) 🔴 Hard

Ссылка: https://leetcode.com/problems/sliding-window-maximum/

Условие: Дан массив 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]

Ограничения:

1 <= nums.length <= 10⁵
-10⁴ <= nums[i] <= 10⁴
1 <= k <= nums.length

💡 Подсказка: Используйте монотонную очередь (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

Объяснение:

dq хранит индексы в порядке убывания значений
dq[0] — индекс максимума текущего окна
Удаляем вышедшие из окна (dq[0] == i - k)
Удаляем меньшие элементы для поддержания монотонности

Сложность:

Время: O(n) — каждый элемент добавляется и удаляется один раз
Память: O(k)

#Задача 7: Shortest Subarray with Sum at Least K (LeetCode 862) 🔴 Hard

Ссылка: https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/

Условие: Дан массив nums (может содержать отрицательные числа) и целое k. Верните длину кратчайшего подмассива с суммой >= k. Если такого нет, верните -1.

Примеры:

Ввод: nums = [1], k = 1
Вывод: 1

Ввод: nums = [1,2], k = 4
Вывод: -1

Ввод: nums = [2,-1,2], k = 3
Вывод: 3

Ограничения:

1 <= nums.length <= 10⁵
-10⁵ <= nums[i] <= 10⁵
1 <= k <= 10⁹

💡 Подсказка: Используйте префиксные суммы и монотонную очередь. Если 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

Объяснение:

prefix[i] — сумма nums[:i]
p - prefix[dq[0]] >= k — нашли подмассив с суммой >= k
prefix[dq[-1]] >= p — удаляем, так как current меньше и новее (лучше для будущих окон)

Сложность:

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

#Задача 8: Remove K Digits (LeetCode 402) 🟦 Medium

Ссылка: https://leetcode.com/problems/remove-k-digits/

Условие: Дана строка num, представляющая неотрицательное целое число, и целое k. Удалите k цифр так, чтобы получить наименьшее возможное число.

Верните результат как строку (без ведущих нулей).

Примеры:

Ввод: num = "1432219", k = 3
Вывод: "1219"
Объяснение: Удалить 4, 3, 2 → "1219"

Ввод: num = "10200", k = 1
Вывод: "200"

Ввод: num = "10", k = 2
Вывод: "0"

Ограничения:

1 <= k <= num.length <= 10⁵
num из цифр 0-9
num не имеет ведущих нулей, кроме "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'

Объяснение:

stack хранит цифры в возрастающем порядке
Пока stack[-1] > digit и k > 0 — удаляем (получаем меньшее число)
lstrip('0') удаляет ведущие нули
Если результат пуст — возвращаем '0'

Сложность:

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

#Задача 9: Create Maximum Number (LeetCode 321) 🔴 Hard

Ссылка: https://leetcode.com/problems/create-maximum-number/

Условие: Даны два массива 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]

Ограничения:

m == nums1.length, n == nums2.length
1 <= m, n <= 500
0 <= nums1[i], nums2[i] <= 9
1 <= k <= m + n

💡 Подсказка: Переберите 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

Объяснение:

max_subsequence: монотонный стек для максимальной подпоследовательности
merge: лексикографическое слияние (сравнение массивов)
Перебираем i от max(0, k-len(nums2)) до min(k, len(nums1))

Сложность:

Время: O(k² × (m + n))
Память: O(k)

#4. Шпаргалка

Задача	Тип	Ключевая идея
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

#5. ⚠️ Common Mistakes

#❌ Ошибка 1: Неправильный порядок в стеке

Проблема: Путают возрастающий и убывающий стек.

# ❌ Неправильно для Next Greater
while stack and stack[-1] < num:  # Возрастающий!
    stack.pop()

# ✅ Правильно — убывающий стек
while stack and stack[-1] < num:  # Выталкиваем меньшие
    idx = stack.pop()
    result[idx] = num

Почему это неправильно: Next Greater требует убывающего стека.

#❌ Ошибка 2: Забыли sentinel для Largest Rectangle

Проблема: Остаток стека не обрабатывается.

# ❌ Неправильно
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 некоторые элементы останутся в стеке.

#❌ Ошибка 3: Неправильная ширина для Largest Rectangle

Проблема: Неверно вычисляют ширину.

# ❌ Неправильно
width = i - stack[-1]  # Забыли -1!

# ✅ Правильно
height = heights[stack.pop()]
width = i if not stack else i - stack[-1] - 1
area = height * width

Почему это неправильно: Ширина = правая граница - левая граница - 1.

#❌ Ошибка 4: Использование стека вместо deque для Sliding Window

Проблема: Стек не поддерживает popleft.

# ❌ Неправильно
stack = []
stack.pop(0)  # O(n) вместо O(1)!

# ✅ Правильно
from collections import deque
dq = deque()
dq.popleft()  # O(1)

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

#❌ Ошибка 5: Пропуск проверки границ в Shortest Subarray

Проблема: Не проверяют пустую очередь.

# ❌ Неправильно
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 может быть пустой.

#6. 🎯 Попробуйте сами

#Задача для самостоятельного решения

Условие: Дан массив температур. Для каждого дня найдите, сколько дней нужно ждать до более тёплой температуры.

Пример:

Ввод: 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 день), ...

💡 Подсказка 1

Используйте убывающий стек для индексов

💡 Подсказка 2

Когда текущая температура > температуры на вершине стека, вычисляем разницу дней

💡 Подсказка 3

Храните индексы в стеке, не значения

✅ Решение

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]

Объяснение:

stack хранит индексы дней с убывающими температурами
Когда находим день теплее, вычисляем разницу для всех меньших
Элементы без более тёплого дня остаются в стеке (result=0)

Сложность:

Время: O(n) — каждый элемент добавляется и удаляется максимум once
Память: O(n) — стек

#7. Заключение

Monotonic Stack/Queue для задач на:

Следующий больший/меньший элемент
Максимум в окне
Площадь в гистограмме
Оптимизация подмассивов

Типы:

Убывающий стек: Next Greater, Remove K Digits
Возрастающий стек: Largest Rectangle
Monotonic Queue: Sliding Window Maximum

Тип

Порядок в стеке

Для чего

Убывающий стек

Большие → Меньшие

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²)

❌ Не применимо

Простота

✅ Простой

⚠️ Сложный

Ввод: 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]

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]

Ввод: 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]

Ввод: 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]

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

Ввод: 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

Ввод: 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]

Ввод: num = "1432219", k = 3 Вывод: "1219" Объяснение: Удалить 4, 3, 2 → "1219" Ввод: num = "10200", k = 1 Вывод: "200" Ввод: num = "10", k = 2 Вывод: "0"

Ввод: 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]

Задача

Тип

Ключевая идея

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