Сложность: medium
Дан циклический массив целых чисел nums (т.е. следующий элемент после nums[nums.length - 1] это nums[0]), верните следующее большее число для каждого элемента в nums.
Следующее большее число для числа x — это первое большее число, следующее за ним в порядке обхода массива, что означает, что вы можете искать циклически, чтобы найти следующее большее число. Если оно не существует, верните -1 для этого числа.
Пример:
Input: nums = [1,2,1]
Output: [2,-1,2]
Explanation: The first 1's next greater number is 2;
The number 2 can't find next greater number.
The second 1's next greater number needs to search circularly, which is also 2.
👨💻 Алгоритм:
1⃣Инициализация
Создайте массив res той же длины, что и nums, и заполните его значениями -1.
2⃣Поиск следующего большего элемента
Для каждого элемента nums[i], используя индекс j, ищите следующий больший элемент среди следующих (циклически) n-1 элементов. Если найден больший элемент, обновите res[i] и прервите внутренний цикл.
3⃣Возврат результата
Верните массив res.
😎 Решение:
class Solution:
def nextGreaterElements(self, nums: List[int]) -> List[int]:
n = len(nums)
res = [-1] * n
for i in range(n):
for j in range(1, n):
if nums[(i + j) % n] > nums[i]:
res[i] = nums[(i + j) % n]
break
return res
Ставь 👍 и забирай 📚 Базу знаний