Сложность: 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 {
public:
int getWinner(vector<int>& arr, int k) {
int maxElement = arr[0];
queue<int> queue;
for (int i = 1; i < arr.size(); i++) {
maxElement = max(maxElement, arr[i]);
queue.push(arr[i]);
}
int curr = arr[0];
int winstreak = 0;
while (!queue.empty()) {
int opponent = queue.front();
queue.pop();
if (curr > opponent) {
queue.push(opponent);
winstreak++;
} else {
queue.push(curr);
curr = opponent;
winstreak = 1;
}
if (winstreak == k || curr == maxElement) {
return curr;
}
}
return -1;
}
};Ставь 👍 и забирай 📚 Базу знаний