今天是第十三天,是队列相关,难度不小
class Solution { public int[] maxSlidingWindow(int[] nums, int k) { int n = nums.length; if(n<2){ return nums; } Deque<Integer> q = new LinkedList(); int[] res = new int[n - k + 1]; for(int i=0; i<n; i++){ while(!q.isEmpty()&&nums[q.peekLast()]<=nums[i]){ q.pollLast(); } q.addLast(i); if(q.peek()<=i-k){ q.poll(); } if(i-k+1>=0){ res[i-k+1] = nums[q.peek()]; } } return res; } }
使用双向队列,遍历数组,如果数组的数大于队列中的数字,那就清空队列,让这个最大值当head,如果再遇到更大的值,以此类推,不然就让比他小的值存在队列尾部。
等二刷在做这道题
今天难度很大,今天的题目得再熟悉一下了。
标签:int,res,最大值,随想录,队列,347,239,第十三天 From: https://www.cnblogs.com/catSoda/p/16820756.html