网站开发方式包括,网站建设实战视频教程,义乌外发饰品加工网,网站建设订制版合同模板思路 滑动窗口 遍历 解题思路 基本思路#xff1a;使用滑动窗口法遍历数组#xff0c;动态维护当前窗口的最大值。 特殊情况#xff1a;该方法有一个缺陷#xff0c;如果出窗口的元素是当前窗口的最大值max时#xff0c;接下来的窗口中的最大值就无法确定了#xff0c;所…思路
滑动窗口 遍历 解题思路
基本思路使用滑动窗口法遍历数组动态维护当前窗口的最大值。 特殊情况该方法有一个缺陷如果出窗口的元素是当前窗口的最大值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-k1,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级别。
