911.在线选举

原题 思路：算出每个时刻的胜者，q函数直接读取结果即可

class TopVotedCandidate:

    def __init__(self, persons: List[int], times: List[int]):
        end = times[-1] #最终时刻
        self.wins = [-1] * (end+1)  #每个时刻的胜者
        maxVote = 0 #当前最高票数
        votes = [0] * len(persons)  #记录每个人的票数
        lastTime = times[0] #上个投票时刻
        # 遍历每个投票时刻
        for i in range(len(times)):  
            time = times[i] #时刻
            person = persons[i] #候选人
            votes[person] += 1
             # (lastTime : time) 这段闭区间的胜者与lastTime时相同
            for i in range(lastTime+1, time):
                self.wins[i] = self.wins[lastTime]
            #当前最高，或者平局，此时产生新胜者
            if votes[person] >= maxVote: 
                maxVote = votes[person]
                self.wins[time] = person
            else:
                self.wins[time] = self.wins[lastTime]
            lastTime = time

    def q(self, t: int) -> int:
        # 注意用例会有超过times[-1]的情况
        return self.wins[t] if t < len(self.wins) else self.wins[-1]