ORID39 Deque window slide

今天做了有关window slide相关题目

[239] 解题报告 window slide

用什么算法？

window slide

为什么用这个算法？

这个算法能够在O（n）的时间内解决问题，而如果不用这个方法，可能要用n^2的时间来解决这道问题

代码实现

这里要注意的是这道题要用deque来解决，因为deque可以把前面不符合条件的问题或者后面不符合条件的数字都去掉。而这道题问题就是给你一个window size，然后在这个window size里面找出最大值并保存，然后返回整个最大值组成的数组。
如果你每走一个index，你都要看一遍这个window 里面最大的数，那就要花费n+k的时间，而不是n。deque可以解决这个问题。就是你用一个for loop

for (int i = 0; i < nums.length; i++) {
      //这一句话实际上就是在把之前加到队列里面的数字看一下，如果小于当前window size， 比如说i当前是5，window size k 是3，那么如果队列q里面
      //有小于5-3+1 也就是3 的数，就把这个数字剔除队列，因为这个数我们已经看过了。）
      while (!q.isEmpty() && q.peek() < i - k + 1) {
          q.poll();
      }
      while (!q.isEmpty() && q.peekLast() < nums[i]) {
            q.pollLast();
       }
      q.offer(i);
      if (i >= k - 1) {
          result[resultIndex++] = q.peek(); //我一开始很迷惑，为什么要用i >= k - 1。后来看了一下给出的例子，就是说这个i在数组的最右边，你走到当前
                                            //window size 最右边的时候，你直接看deque里面的第一个数字就好了，因为之前两个while loop已经帮你把小的数字和多余的数字给解决了。
      }
}
return result;