題目來源

力扣每日一題；題序：1535

我的題解

方法一 純模擬

排除一種情況：當k>=n-1時，至少會遍歷數組一遍，實質就是求數組的最大值。
其余的情況使用List來進行模擬操作

時間復雜度：
空間復雜度：

public int getWinner(int[] arr, int k) {int n=arr.length;//若需要循環一輪，則必然是最大那個值if(k>=n-1)return Arrays.stream(arr).max().getAsInt();List<Integer> list=new ArrayList<>();for(int i=0;i<n;i++)list.add(arr[i]);int res=Math.max(arr[0],arr[1]);while(true){//記錄連續的次數int t=k;//保存上一個最大值int pre=0;int t1=list.get(0),t2=list.get(1);if(t1>t2){pre=t1;list.remove(1);list.add(t2);}else{pre=t2;list.remove(0);list.add(t1);}t--;while(t>0){t1=list.get(0);t2=list.get(1);int curP=Math.max(t1,t2);//若最大值與上一次相同，表示連續，連續次數減1if(curP==pre){t--;//否則需要以新的最大值重新開始}else{break;}if(t1>t2){list.remove(1);list.add(t2);}else{list.remove(0);list.add(t1);}}if(t==0){res=pre;break;}}return res;
}

方法二 一次遍歷

實質只需要一次遍歷比較就能知道答案

時間復雜度：O(n)
空間復雜度：O(1)

public int getWinner(int[] arr, int k) {int n=arr.length;int max=arr[0];for(int i=1,count=0;i<n;i++){if(max<arr[i]){max=arr[i];count=1;}else{count++;}if(count==k){break;}}return max;
}

有任何問題，歡迎評論區交流，歡迎評論區提供其它解題思路（代碼），也可以點個贊支持一下作者哈😄~