Leetcode每日一题-20241024

原题链接：找到连续赢K场比赛的第一位玩家

如果直接模拟比赛的要求，用玩家的编号创建队列（deque），并初始化一个哈希表记录每个玩家取得的胜场。每次取出前两个玩家的编号，对比skills值，更大的插入队首，更小的插入队尾，同时将胜出的玩家胜场加1，如果胜场达到k场则直接返回该玩家编号。

class Solution:
    def findWinningPlayer(self, skills: List[int], k: int) -> int:
        n = len(skills)
        play = deque(list(range(n)))
        winner = {i: 0 for i in range(n)}
        while True:
            p1, p2 = play.popleft(), play.popleft()
            if skills[p1] > skills[p2]:
                play.appendleft(p1)
                play.append(p2)
                winner[p1] += 1
                if winner[p1] >= k:
                    return p1
            else:
                play.appendleft(p2)
                play.append(p1)
                winner[p2] += 1
                if winner[p2] >= k:
                    return p2

但是这样发现还是会超时。思考后发现，这种比赛方式只要进行第一轮（n位玩家都进行过比赛）还没有结束，那么后续都只可能是技能等级最高的玩家胜出，因此进行一轮比赛仍未结束，就可以直接返回队首的玩家编号。上面就不需要用while True了。修改如下：

class Solution:
    def findWinningPlayer(self, skills: List[int], k: int) -> int:
        n = len(skills)
        play = deque(list(range(n)))
        winner = {i: 0 for i in range(n)}
        play_num = 0
        while play_num < n:
            p1, p2 = play.popleft(), play.popleft()
            if skills[p1] > skills[p2]:
                play.appendleft(p1)
                play.append(p2)
                winner[p1] += 1
                if winner[p1] >= k:
                    return p1
            else:
                play.appendleft(p2)
                play.append(p1)
                winner[p2] += 1
                if winner[p2] >= k:
                    return p2
            play_num += 1
        return play[0]
            

时间复杂度和空间复杂度均为O(n)。查看题解后发现，其实空间复杂度是可以优化的，遍历过程中，输过的玩家不可能是赢家了，因此完全不需要记录所有玩家的胜场。