Почему это работает
- Число ждёт в стеке, пока не придёт первое число больше; оно его и снимает — это и есть следующее большее. В стеке числа к верху только убывают, поэтому большее снимает их сверху вниз, и цикл останавливается на первом, которое не меньше нового.
- Все числа различны, поэтому ключом словаря может быть само число, и в стеке можно держать числа, а не индексы.
- У числа, оставшегося в стеке в конце, дальше нет большего. В словарь оно не попадает, и поиск даёт -1.
Сложность
Время O(n + m), где n — длина nums2, m — длина nums1: каждое число из nums2 кладётся в стек один раз и снимается не больше одного раза, а поиск в словаре — O(1). Память O(n) на словарь и стек.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗