JAVA算法练习题day9

11.滑动窗口最大值

看题解写的。双头队列（单调队列），他一步一步分析的思路值得学习模仿。

(239. 滑动窗口最大值 - 力扣（LeetCode）)

class Solution {public int[] maxSlidingWindow(int[] nums, int k) {//非严格单调减的队列int[] ans = new int[nums.length-k+1];Deque<Integer> window = new LinkedList<>();//right [0,n-1](因为要处理第一个元素nums[0]的入队，所以right的初始值就指向0)//int right = 0;//left [-k+1,n-1-k+1]; +1就是因为刚开始时候right已经有一个数了//int left = -k+1;//因为是一起自增的，left的自增可以写进for里面for(int right = 0,left = 1-k;right<nums.length;right++,left++){//维护窗口大小为K，实现删除元素,left>0表示此次循环(循环开始前left++，所以应当是nums[left-1]出队)应当有元素随着本次窗口的滑动。被移除if(left>0 && nums[left-1]==window.peekFirst()) window.removeFirst();//维护单调减队列,怎么实现插队后，删除插队位置后面的所有元素:因为是持续删除插队位置后面的所有元素，所以用while//这里的if怎么写while(!window.isEmpty() && nums[right]>window.peekLast() ){window.removeLast();}//while完成后将右移得到的新元素加入队列window.addLast(nums[right]);//当左边界有效时，记录答案 队首if(left>=0){ans[left]=window.peekFirst();}}return ans;}
}

题解各个方法中，单调队列的做法最优，先掌握这个，其他模型到了经典例题时候再学（大根堆之类的）。今天19.02就完成了算法题的学习和练习。继续加油。