[每日一题] 1535.找出数组游戏的赢家

2024 年 05 月 19 日

99 次浏览

1933字数

> https://leetcode.cn/problems/find-the-winner-of-an-array-game/description/?envType=daily-question&envId=2024-05-02

`arr` 中的数各不相同，所以每场比赛一定可以分出胜负，很容易想到用双端队列模拟。`arr` 最大为 $10^5$ ，数据规模在可接受范围内。但 `k` 最大为 $10^9$ ，不能模拟到底。观察题目很容易看出当 `k` 比 `arr` 的长度大时，赢家一定是 `arr` 中最大的那个数，因此代码如下：

```c++
class Solution {
public:
    int getWinner(std::vector<int>& arr, int k) {
        const int n = arr.size();
        if (k >= n)
            return *std::max_element(arr.begin(), arr.end());

std::deque<int> compete(arr.begin(), arr.end());

int victory = 0;
        while (victory < k) {
            int first = compete.front();
            compete.pop_front();
            int second = compete.front();
            compete.pop_front();

if (first > second) {
                victory++;
                compete.push_front(first);
                compete.push_back(second);
            } else {
                victory = 1;
                compete.push_front(second);
                compete.push_back(first);
            }
        }
      
        return compete.front();
    }
};
```

- 时间复杂度：$O(n + k)$ ，其中 $n$ 为 `arr` 数组的长度。
- 空间复杂度：$O(n)$ 。

上述代码还有进一步优化的空间。易知每场比赛都是之前的胜者和 `arr[i] (i > 2)` 进行比较，并且如果遍历完 `arr` 还没有找出连续胜利 `k` 轮的数的话，最终的胜者一定是 `arr` 中最大的数。因此可以优化如下：

```c++
class Solution {
public:
    int getWinner(std::vector<int>& arr, int k) {
        const int n = arr.size();

int curMax = std::max(arr[0], arr[1]);
        if (k == 1)
            return curMax;

int victory = 1;
        for (int i = 2; i < n; i++) {
            if (arr[i] > curMax) {
                curMax = arr[i];
                victory = 1;
            } else {
                victory++;
                if (victory == k)
                    return curMax;
            }
        }

return curMax;
    }
};
```

- 时间复杂度：$O(n)$ ，其中 $n$ 为 `arr` 数组的长度。
- 空间复杂度：$O(1)$ 。

最后修改：2024 年 05 月 19 日