网站地图的形式,软件项目管理的主要内容包括哪些,深圳工业设计师工资一般多少,做citation的网站问题
给你一个整数数组 nums#xff0c;有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
示例 1#xff1a;
输入#xff1a;nums [1,3,-1,-3,5,3,6,7], …
问题
给你一个整数数组 nums有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
示例 1
输入nums [1,3,-1,-3,5,3,6,7], k 3
输出[3,3,5,5,6,7]
解释
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 31 [3 -1 -3] 5 3 6 7 31 3 [-1 -3 5] 3 6 7 51 3 -1 [-3 5 3] 6 7 51 3 -1 -3 [5 3 6] 7 61 3 -1 -3 5 [3 6 7] 7示例 2
输入nums [1], k 1
输出[1]提示
1 nums.length 105-104 nums[i] 1041 k nums.length
思路
本题虽然标签是困难但是个人认为只要想清楚了思路其实也还好我一开始想的是直接暴力遍历但是没有考虑到一些特殊的条件比如k1或者其他边界条件所以导致我没过这里也附上代码供各位赏玩~ public int[] maxSlidingWindow(int[] nums, int k) {int lIndex0,rIndexk;int[] result new int[100002];int lennums.length,maxi-99999,index0;while(rIndexlen){for(int ilIndex;irIndex;i){maxiMath.max(nums[i],maxi);}result[index]maxi;lIndex;rIndex;}int[] re new int[index];for(int i0;iindex;i){re[i]result[i];}return re;}
可能大部分友友想的最多的就是我上面这种使用暴力解决但是这是一种暴力解法且没过所以我后面又换了一种思路就是使用双端队列来解决大概思路就是在队列中存储下标值然后对于每一个当前加入的值去判断队列最后一个值是否小于当前值如果小于就移除队列同时我们需要去更新队列中小于当前下标-k的下标进行移除当窗口大小达到最大值后去记录最大值。 public int[] maxSlidingWindow(int[] nums, int k){// 设置双端队列存储数据DequeInteger deque new LinkedList();int len nums.length;int[] result new int[len-k1];for(int i0;ilen;i){// 移除掉队列中比当前值小的下标while(!deque.isEmpty()nums[deque.peekLast()]nums[i]){deque.pollLast();}//将当前下标存入队列中deque.offerLast(i);// 移除队列中不在i-k中的元素if(deque.peekFirst()i-k){deque.pollFirst();}// 当窗口大小达到k时记录最大值if(ik-1){result[i-k1]nums[deque.peekFirst()];}}return result;}
代码中均做有注解不懂的地方可以评论区提问我们共同学习~
