给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
方法一：使用大根堆 （搞复杂了）
public static int[] maxSlidingWindow1(int[] nums, int k) { if(nums.length <= 0){ return new int[0]; } //创建大堆根 Queue<Integer> priority = new PriorityQueue<>((x1 , x2)->x2 - x1); List<Integer> listInt = new ArrayList<>(); int i , j = 0 , pre; pre = nums[j]; for(i = 0 ; i < k ; i++){ priority.offer(nums[i]); } listInt.add(priority.peek()); for (i = k ; i < nums.length ; i++){ priority.remove(pre); priority.offer(nums[i]); listInt.add(priority.peek()); pre = nums[++j]; } int[] _nums = new int[listInt.size()]; for (i = 0 ; i < _nums.length ; i++){ _nums[i] = listInt.get(i); } return _nums; }方法二：双端队列
public static int[] maxSlidingWindow2(int[] nums, int k){ if(nums.length <= 0){ return new int[0]; } //双端队列 顺序保存 从大到小 Deque<Integer> deQue = new LinkedList<>(); int[] res = new int[nums.length - k + 1]; int i = 0 , j = 0; int index = 0; for(j = 0 ; j < k ; j++){ while (!deQue.isEmpty() && deQue.getLast() < nums[j]) deQue.pollLast(); deQue.offer(nums[j]); } //j和i同时移动 int value = 0; for(i = 0 , j = k ; j < nums.length ; j++ , i++){ value = deQue.getFirst(); res[index++] = value; //如果双端队列头和窗口最最左边大小相等，则移除 if(value == nums[i]){ deQue.pollFirst(); } //保持队列从大到小的顺序 while (!deQue.isEmpty() && deQue.getLast() < nums[j]) deQue.pollLast(); deQue.offer(nums[j]); } if(!deQue.isEmpty()){ res[index++] = deQue.getFirst(); } return res; }
题解：https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/solution/
