思路
滑動窗口 + 遍歷
解題思路
基本思路：使用滑動窗口法遍歷數組，動態維護當前窗口的最大值。 特殊情況：該方法有一個缺陷，如果出窗口的元素是當前窗口的最大值max時，接下來的窗口中的最大值就無法確定了，所以就需要遍歷新窗口，尋找其中的最大值。
復雜度
- 時間復雜度: O(N * K)
- 空間復雜度: O(N)
代碼實現：
class Solution {public int[] maxSlidingWindow(int[] nums, int k) {int n = nums.length;int[] maxNum = new int[n - k + 1];int right = 0; int max = nums[0]; //記錄窗口的最大值int index = 0; //記錄最大值的下標//初始化窗口while(right < k){if(nums[right] >= max){max = nums[right];index = right;}right++;}maxNum[0] = max;//滑動窗口while(right < n){//如果入窗口的元素成為最大值則更新max和indexif(nums[right] >= max){max = nums[right];index = right;}//如果出窗口的元素為最大值，則需要重新尋找當前窗口的最大值及下標if(right-k == index){int[] newMax = findMax(nums,right-k+1,k);max = newMax[0];index = newMax[1];}maxNum[right - k + 1] = max;right++;}return maxNum;}//尋找當前窗口的最大值及其下標public int[] findMax(int[] nums, int start, int k){int[] max = new int[2];max[0] = nums[start];max[1] = start;for(int i = start + 1; i < start + k; i++){if(nums[i] >= max[0]){max[0] = nums[i];max[1] = i;}}return max;}
}在我第一次寫的時候直接就在每個窗口中加findMax函數無腦遍歷，運行后發現超時，代碼時間復雜度是 O(N * K)。隨后按自己想法改了改代碼，改成現在這個，最壞時間復雜度還是O(N * K)，但是再一次運行發現可以通過。后面看了看官方題解，題解一的思路和我的大致一樣但是用了優先級隊列，運行速度方面能比自己的快，主要區別在于自己的findMax函數用遍歷的方式找最大值及下標，優先級隊列底層則用的堆，其復雜度為logN級別。
)
)
