Сложность: medium
Дан целочисленный массив
arr из различных целых чисел и целое число k.Игра будет проводиться между первыми двумя элементами массива (т.е.
arr[0] и arr[1]). В каждом раунде игры мы сравниваем arr[0] с arr[1], большее число побеждает и остается на позиции 0, а меньшее число перемещается в конец массива. Игра заканчивается, когда одно число выигрывает k подряд раундов.Верните число, которое выиграет игру.
Гарантируется, что у игры будет победитель.
Пример:
Input: arr = [2,1,3,5,4,6,7], k = 2
Output: 5
Explanation: Let's see the rounds of the game:
Round | arr | winner | win_count
1 | [2,1,3,5,4,6,7] | 2 | 1
2 | [2,3,5,4,6,7,1] | 3 | 1
3 | [3,5,4,6,7,1,2] | 5 | 1
4 | [5,4,6,7,1,2,3] | 5 | 2
So we can see that 4 rounds will be played and 5 is the winner because it wins 2 consecutive games.
👨💻 Алгоритм:
1⃣Инициализируйте maxElement как максимальный элемент в arr, queue как очередь с элементами массива, кроме первого, curr = arr[0] и winstreak = 0.
2⃣Пока очередь не пуста (или используйте бесконечный цикл), извлеките opponent из начала очереди. Если curr > opponent, добавьте opponent в конец очереди и увеличьте winstreak на 1. В противном случае добавьте curr в конец очереди, установите curr = opponent и winstreak = 1.
3⃣Если winstreak = k или curr = maxElement, верните curr. Код никогда не должен достигать этой точки, так как гарантированно есть победитель. Верните любое значение.
😎 Решение:
class Solution {
function getWinner($arr, $k) {
$maxElement = $arr[0];
$queue = array_slice($arr, 1);
for ($i = 1; $i < count($arr); $i++) {
$maxElement = max($maxElement, $arr[$i]);
}
$curr = $arr[0];
$winstreak = 0;
while (!empty($queue)) {
$opponent = array_shift($queue);
if ($curr > $opponent) {
array_push($queue, $opponent);
$winstreak++;
} else {
array_push($queue, $curr);
$curr = $opponent;
$winstreak = 1;
}
if ($winstreak == $k || $curr == $maxElement) {
return $curr;
}
}
return -1;
}
}Ставь 👍 и забирай 📚 Базу знаний