Сложность: 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 {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
int n = nums.size();
vector<int> res(n, -1);
for (int i = 0; i < n; i++) {
for (int j = 1; j < n; j++) {
if (nums[(i + j) % n] > nums[i]) {
res[i] = nums[(i + j) % n];
break;
}
}
}
return res;
}
};Ставь 👍 и забирай 📚 Базу знаний