Readme

649.Dota2-Senate

对于R来说，其最优的策略是消灭其身后第一个仍存活的D，如果没有，再从队首开始找第一个仍存活的D。

此题如果依此策略进行模拟的话，效率很低。有比较巧妙的贪心算法，可以o(n)得到结果。

设置一个字符串s，代表senate经过一轮厮杀之后得以存活进入下一轮的子串。那么怎么从senate快捷方便地得到s呢？我们设置一个计数器count，如果遇到R就加一，遇到D就减一。注意，如果遇到R的时候，count>=0，说明之前的所有R/D厮杀得到的结果是R净胜，说明当前的R是不会被之前的任何D所封禁的，所以可以放心地将R加入s中。反之，如果遇到D的时候，count<=0，说明之前的所有R/D厮杀得到的结果是D净胜，说明当前的D是不会被之前的任何R所封禁的，所以可以放心地将D加入s中。其他情况下，都说明当前的R或D都无法能够存活，不能被加入下一轮的s中。

扫完一轮之后，接下来的关键点是：更新senate为s，但count不清零，重复上述的步骤。这是因为上一轮末的count其实反映了队尾存留的R的数目（或者D），他们能可以封禁残存的位于队首的D（或者R）。

最后循环直到新生成的s的长度不再变化，说明此时的s里面全部都是R或者D了。

Leetcode Link