Задача: 503. Next Greater Element II
Дан циклический массив целых чисел 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 {
function nextGreaterElements($nums) {
$n = count($nums);
$res = array_fill(0, $n, -1);
for ($i = 0; $i < $n; $i++) {
for ($j = 1; $j < $n; $j++) {
if ($nums[($i + $j) % $n] > $nums[$i]) {
$res[$i] = $nums[($i + $j) % $n];
break;
}
}
}
return $res;
}
}👉Новости 👉База вопросов
