Сложность: 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 {
func nextGreaterElements(_ nums: [Int]) -> [Int] {
let n = nums.count
var res = [Int](repeating: -1, count: n)
for i in 0..<n {
for j in 1..<n {
if nums[(i + j) % n] > nums[i] {
res[i] = nums[(i + j) % n]
break
}
}
}
return res
}
}Ставь 👍 и забирай 📚 Базу знаний