html简单网站成品免费,重庆建工集团,网站建设 h5 小程序,网站开发流程步骤题目信息
LeetoCode地址: . - 力扣#xff08;LeetCode#xff09;
题目理解
题意是很好理解的#xff0c;一个固定长度(k)的滑块从一个数组的左端一步一步向右滑#xff0c;然后挑出滑块盖住的那些数字中最大的#xff0c;组成的数组就是结果。
难点在于#xff0c;…题目信息
LeetoCode地址: . - 力扣LeetCode
题目理解
题意是很好理解的一个固定长度(k)的滑块从一个数组的左端一步一步向右滑然后挑出滑块盖住的那些数字中最大的组成的数组就是结果。
难点在于当滑块移动时左端的数字会被遗弃如果遗弃的刚好是最大的数字则要从剩下的k-1个元素以及右端新覆盖的元素里找到最大的。想要让时间复杂度低需要找到一种低成本的方式维护这些数字的有序性。这样即便最大的元素遗弃了第二大的元素也唾手可得。
如何得到一个单调递减的元素列 array呢假设当前滑块的左下标是l右下标是r.
好我们从下标il开始遍历一开始元素列是空的直接将i下标存进去。
array [i]
i递增来到i1.此时有两种情况
i1下标对应的元素比array最后一个元素小i1下标对应的元素与array最后一个元素一样大i1下标对应的元素比array最后一个元素大
对第一种和第二种情况直接将其存入array因为我们需要的就是单调递减的array。
对第三种情况如果存入则违反了单调递减所以我们要从array尾部一直弹出元素直到array为空或者array尾部下标对应的元素比i1对应的元素要更大。
这里可能有人会想不明白如果将元素都弹出了有没有可能找不到最大元素其实不然我们在找最大元素时永远都是从array中取第一个元素我们永远都会取到最大元素。
发现了嘛我们是通过单调栈的方式使数组最终有序的在这个过程中我们遗弃了那些一定不会用到的元素。
当滑块向右移动时原理是类似的array中元素下标小于新l的元素需要从队首弹出而新r对应的加入的元素需要遵循同样的方式从队尾插入array。 单调栈单调队列
在nums长度为l滑块长度为k的情况下
时间复杂度: O(l), 滑块至多移动l-k次每次移动中元素只会进出queue一次。
额外空间复杂度:O(k), 至多需要k长度的队列存储单调递减的数列。
public int[] maxSlidingWindow(int[] nums, int k) {// 题目理解中的array使用 一个双端队列实现LinkedListInteger queue new LinkedList();int length nums.length;int[] res new int[length-k1];// 对于头k个元素需要初始化入队操作for (int i 0; i k; i) {// 递归单调出栈直到队空或者队尾大于当前元素while (!queue.isEmpty() nums[queue.peekLast()] nums[i]) {queue.pollLast();}// 插入新队尾元素queue.offerLast(i);}// 此时初始化完成的队列头元素就是第一个最大值res[0] nums[queue.peekFirst()];// l 和 r 模拟滑块的左右两端int l 1, r lk-1;//模拟滑块的移动操作while (r length) {// 由于l持续右移需要将array中队头小于l的元素移除while (!queue.isEmpty() queue.peekFirst() l) {queue.pollFirst();}// 重复单调出栈以及入栈的操作保持队列单调递减while (!queue.isEmpty() nums[queue.peekLast()] nums[r]) {queue.pollLast();}queue.offerLast(r);res[l] nums[queue.peekFirst()];l;r;}return res;}
