题解 | 参议院投票

class Solution:
    def predictVictory(self , s: str) -> str:
        n = len(s)
        stackR = []
        stackD = []
        for i in range(n):#时间复杂度O(n)
            f, s = s[0], s[1:]
            if f == 'R':
                stackR.append(i) #生成Red栈
            else:
                stackD.append(i) #生成Dark栈

        while stackR and stackD:#时间复杂度O(n)
            if stackR[0] > stackD[0]:
                stackR.pop(0) #投票出人
                s1 = stackD.pop(0)+n
                stackD.append(s1) #投票者这轮用过投票权，但未出局，下一轮仍可投票，加n下一轮排队等号
            else: 
                s2 = stackR.pop(0)+n
                stackD.pop(0)
                stackR.append(s2)

        if stackR:
            return 'Red'
        if stackD:
            return 'Dark'