网站导航条图片素材,百度信息流推广教程,成立公司的好处和坏处,wordpress自动采集发布文章目录题目描述思路 代码1. 暴力法 O(n2n^2n2) O(1)2. 单调队列辅助 O(n) O(n)二刷打卡第十天#xff5e; 题目描述
久违的滑动窗口题#xff01;
思路 代码
1. 暴力法 O(n2n^2n2) O(1)
老规矩#xff0c;先…
文章目录题目描述思路 代码1. 暴力法 O(n2n^2n2) O(1)2. 单调队列辅助 O(n) O(n)二刷打卡第十天 题目描述
久违的滑动窗口题
思路 代码
1. 暴力法 O(n2n^2n2) O(1)
老规矩先来个暴力法熟悉一下题目出乎意料没有超时…不过我们还是需要寻找更优的做法
class Solution {public int[] maxSlidingWindow(int[] nums, int k) {if(nums.length 0) {return new int[]{};}int[] res new int[nums.length - k 1];// 暴力for(int i 0; i res.length; i) {int max nums[i];for(int j 0; j k; j) {max Math.max(max, nums[i j]);}res[i] max; } return res;}
}2. 单调队列辅助 O(n) O(n)
空间换时间利用一个单调递减的队列始终把当前滑动窗口最大值置于队头更新判断一当前队头是否已经脱离滑动窗口。我觉得这块具体代码不太好想到更新判断二加入当前数组元素是否会改变队列递减特性
class Solution {public int[] maxSlidingWindow(int[] nums, int k) {if(nums.length 0) {return new int[]{};}// 队列头记录滑动窗口最大值DequeInteger deque new LinkedList();int[] res new int[nums.length - k 1];for(int i 0, windowTail 1 - k; i nums.length; i, windowTail) {// 更新一去掉前一个窗口尾值if(windowTail 0 deque.peekFirst() nums[windowTail - 1]) {deque.removeFirst();}// 更新二保持递减while(!deque.isEmpty() deque.peekLast() nums[i]) {deque.removeLast();}deque.addLast(nums[i]);// 记录窗口最大值if(windowTail 0) {// 窗户尾值同时也是 res 的对应下标res[windowTail] deque.peekFirst();}}return res;}
}/*1. 采用单调队列2. 主要是 队列头 的处理3. 通过维护 windowTail 来维护队列重要
*/二刷
单调队列找最大值则需要单调减队头为最大
class Solution {public int[] maxSlidingWindow(int[] nums, int k) {if(nums.length 0) {return new int[]{};}int[] ans new int[nums.length - k 1];DequeInteger queue new ArrayDeque();for(int i 0, windowTail 1 - k; i nums.length; i, windowTail) {// step1: 去掉上一个窗口尾值if(windowTail 0 queue.element() nums[windowTail - 1]) {queue.poll();}// step2: 保持递减注意没有按照正常的队列顺序是从后面开始处理的while(!queue.isEmpty() nums[i] queue.getLast()) {queue.removeLast();}queue.offer(nums[i]);if(windowTail 0) {ans[windowTail] queue.element();}}return ans;}
}
