Next Greater Element I

Условие

Даны два массива целых чисел nums1 и nums2, где элементы в nums1 являются подмножеством nums2, и в обоих массивах нет повторяющихся элементов. Для каждого элемента nums1 нужно найти первый элемент справа от него в nums2, который больше текущего. Если такого элемента нет, вернуть -1 для этого числа.

Верни массив, в котором для каждого элемента из nums1 указан его следующий больший элемент из nums2, либо -1, если такого нет.

Примеры

Input: nums1 = [4, 1, 2], nums2 = [1, 3, 4, 2]

Output: [-1, 3, -1]

Explanation: Для 4 нет большего элемента справа, для 1 следующий больший элемент — 3, для 2 нет большего элемента справа.

Input: nums1 = [2, 4], nums2 = [1, 2, 3, 4]

Output: [3, -1]

Explanation: Для 2 следующий больший элемент — 3, для 4 нет большего элемента справа.

Решение

fun nextGreaterElement(nums1: IntArray, nums2: IntArray): IntArray {
    val nextGreaterMap = mutableMapOf<Int, Int>()
    val stack = mutableListOf<Int>()

    // Проходим по элементам nums2 и находим следующий больший элемент для каждого
    for (num in nums2) {
        // Если текущий элемент больше элемента на вершине стека, обновляем следующий больший элемент
        while (stack.isNotEmpty() && stack.last() < num) {
            nextGreaterMap[stack.removeAt(stack.size - 1)] = num
        }
        stack.add(num)  // Добавляем текущий элемент в стек
    }

    // Если для элемента нет большего справа, устанавливаем -1
    for (num in stack) {
        nextGreaterMap[num] = -1
    }

    // Заполняем результат для nums1 на основе построенного словаря
    return nums1.map { nextGreaterMap[it] ?: -1 }.toIntArray()
}

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

O(n + m), где n — длина nums2, а m — длина nums1, так как мы проходим по каждому элементу массива nums2 один раз, а также создаем результат для nums1.

Пространственная сложность

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