力扣 239.滑动窗口最大值

思路

滑动窗口 + 遍历

解题思路

基本思路：使用滑动窗口法遍历数组，动态维护当前窗口的最大值。 特殊情况：该方法有一个缺陷，如果出窗口的元素是当前窗口的最大值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级别。