<p>A competition consists of <code>n</code> players numbered from <code>0</code> to <code>n - 1</code>.</p>

<p>You are given an integer array <code>skills</code> of size <code>n</code> and a <strong>positive</strong> integer <code>k</code>, where <code>skills[i]</code> is the skill level of player <code>i</code>. All integers in <code>skills</code> are <strong>unique</strong>.</p>

<p>All players are standing in a queue in order from player <code>0</code> to player <code>n - 1</code>.</p>

<p>The competition process is as follows:</p>

<ul>
	<li>The first two players in the queue play a game, and the player with the <strong>higher</strong> skill level wins.</li>
	<li>After the game, the winner stays at the beginning of the queue, and the loser goes to the end of it.</li>
</ul>

<p>The winner of the competition is the <strong>first</strong> player who wins <code>k</code> games <strong>in a row</strong>.</p>

<p>Return the initial index of the <em>winning</em> player.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">skills = [4,2,6,3,9], k = 2</span></p>

<p><strong>Output:</strong> 2</p>

<p><strong>Explanation:</strong></p>

<p>Initially, the queue of players is <code>[0,1,2,3,4]</code>. The following process happens:</p>

<ul>
	<li>Players 0 and 1 play a game, since the skill of player 0 is higher than that of player 1, player 0 wins. The resulting queue is <code>[0,2,3,4,1]</code>.</li>
	<li>Players 0 and 2 play a game, since the skill of player 2 is higher than that of player 0, player 2 wins. The resulting queue is <code>[2,3,4,1,0]</code>.</li>
	<li>Players 2 and 3 play a game, since the skill of player 2 is higher than that of player 3, player 2 wins. The resulting queue is <code>[2,4,1,0,3]</code>.</li>
</ul>

<p>Player 2 won <code>k = 2</code> games in a row, so the winner is player 2.</p>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">skills = [2,5,4], k = 3</span></p>

<p><strong>Output:</strong> 1</p>

<p><strong>Explanation:</strong></p>

<p>Initially, the queue of players is <code>[0,1,2]</code>. The following process happens:</p>

<ul>
	<li>Players 0 and 1 play a game, since the skill of player 1 is higher than that of player 0, player 1 wins. The resulting queue is <code>[1,2,0]</code>.</li>
	<li>Players 1 and 2 play a game, since the skill of player 1 is higher than that of player 2, player 1 wins. The resulting queue is <code>[1,0,2]</code>.</li>
	<li>Players 1 and 0 play a game, since the skill of player 1 is higher than that of player 0, player 1 wins. The resulting queue is <code>[1,2,0]</code>.</li>
</ul>

<p>Player 1 won <code>k = 3</code> games in a row, so the winner is player 1.</p>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == skills.length</code></li>
	<li><code>2 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= k &lt;= 10<sup>9</sup></code></li>
	<li><code>1 &lt;= skills[i] &lt;= 10<sup>6</sup></code></li>
	<li>All integers in <code>skills</code> are unique.</li>
</ul>

class Solution:
    def findWinningPlayer(self, skills: List[int], k: int) -> int:
        # 连续递增数列的index
        # 每个index左边只能赢一次，右边赢下一个比他大的index之间的所有数的次数
        if len(skills) <= k:
            return skills.index(max(skills))
        stack=[]
        l=len(skills)
        stack.append(0)
        for i in range(1,l):
            if skills[i]>skills[stack[-1]]:
                stack.append(i)
        max_index=stack[-1]
        if max_index==0:
            return 0
        pre_index=None
        while stack:
            index=stack.pop(0)
            win_times=0
            if pre_index != None:
                win_times=index-pre_index-1
                if pre_index > 0:
                    win_times+=1
            if win_times>=k:
                return pre_index
            pre_index=index
        return max_index
         
            
            
        #  one case time exceeded
        # l=len(skills)
        # dictionary={}
        # for i in range(l):
        #     dictionary[skills[i]]=[i,0]
        # maxi=None
        # operations=0
        # max_item=max(skills)
        # while skills and operations<l:
        #     if maxi==None:
        #         player1=skills.pop(0)
        #         player2=skills.pop(0)
        #         if player1>player2:
        #             maxi=player1
        #             dictionary[player1][1]+=1
        #             if dictionary[player1][1]>=k:
        #                 return dictionary[player1][0]
        #             skills.append(player2)
        #         else:
        #             maxi=player2
        #             dictionary[player2][1]+=1
        #             if dictionary[player2][1]>=k:
        #                 return dictionary[player2][0]
        #             skills.append(player1)
        #     else:
        #         player2=skills.pop(0)
        #         if maxi>player2:
        #             dictionary[maxi][1]+=1
        #             if dictionary[maxi][1]>=k:
        #                 return dictionary[maxi][0]
        #             skills.append(player2)
        #         else:
        #             dictionary[player2][1]+=1
        #             if dictionary[player2][1]>=k:
        #                 return dictionary[player2][0]
        #             skills.append(maxi)
        #             maxi=player2
        #     operations+=1
        # return dictionary[max_item][0]
        
1285