239.滑动窗口最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3 输出：[3,3,5,5,6,7]

1. Deque是LinkedList类实现的一个双端队列的接口，Deque<Integer> deque=new LinkedList<>()。

• 	首元素	首元素	尾元素	尾元素
  	抛出异常	特殊值	抛出异常	特殊值
  插入	addFirst(e)	offerFirst(e)	addLast(e)	offerLast(e)
  删除	removeFirst()	pollFirst()	removeLast()	pollLast()
  检查	getFirst()	peekFirst()	getLast()	peekLast()

2. 一开始看到滑动窗口先想到动规，但是这题动规的开销比较大。开辟O(n^2)空间数组来保存状态。dp[i][j]表示下标从i到j的最大值。则dp[i][j]=Math.max(dp[i][j-1]，dp[i+1][j])，可以初始化第0行和第n列以及dp[i][i],然后需要从下往上，从左往右遍历来维护dp。
3. 固定窗口+最大值自然要能想到大根堆。其实就是一个有序的双端队列，这里队列存放的是数组的索引下标，每次窗口滑动进来一个元素出去一个元素。有两个问题需要考虑：

• 每次窗口移动时，堆顶元素最大值要考虑在不在当前窗口内，因此每次窗口滑动若当前队列的最大值的索引下标小于当前窗口的左边界则移出。

• 插入新元素时，要保证插入后队列保持有序。如果每次插入都是从小(队尾)到大(头)找到相应的位置插入，那么排序时间O(logn)(PriorityQueue底层基于堆实现)，总的时间复杂度O(nlogn)。

  实际上每次插入时，队列中比待插入元素小的都可以直接出队，因为插入元素肯定是在当前窗口的右边界，索引下标在比它小的元素的右边，所以该元素进队后肯定是轮不到比它小的元素作为最大元素出队的。因此可以直接出队，每个元素只进入一次队列出一次队列(被访问就要出)，因此排序时间O(1)，总时间O(n)。

 public int[] maxSlidingWindow(int[] nums, int k) {
 Deque<Integer> queue=new LinkedList<>();
     int[] res=new int[nums.length-k+1];
     for(int i=0;i<nums.length;i++)
     {
     while(!queue.isEmpty()&&queue.peek()<i-k+1) queue.poll();
     while(!queue.isEmpty()&&nums[queue.peekLast()]<nums[i]) queue.pollLast();
     queue.offer(i);
     if(i>=k-1)
     res[i-k+1]=nums[queue.peek()];
     }
 	return res;
   }