239. 滑动窗口最大值

题目链接：力扣

思路

       这道题目暴力解法是很容易写出来的，但是暴力解法的时间复杂度为O(n*k)（n为遍历数组的长度，k为遍历滑动窗口的长度），会超出时间限制。

 所以我们需要降低时间复杂度，遍历数组是不可避免的，如果获取滑动窗口中的最大值时间复杂度为O(1)就可以了

       对于在加入的同时我们能求出最大值，首先可能想到的是优先队列，也就是大顶堆，但是滑动窗口的最大值是不断更新的，所以是不太适合的，要想整也是可以的,时间复杂度为O(n*logk)

       这里使用一种叫做单调队列的思想：对这道题目来说，希望这个队列中的数字一直是单调递减的，这样每次站在队头的就是最大值

       因为没有单调队列这样的数据结构，所以我们需要实现单调队列，对于这个题目：

               1、实现获取最大值的功能getMaxNum() -- 获取队列的队头就可以

               2、实现窗口的滑动poll() -- 移动窗口：①当移动窗口的时候，队头的值如果还是上一个窗口的第一个值（说明上一个滑动窗口的第一个值就是最大值）的时候，就需要将此数poll(）；②如果不是上一个窗口的第一个值，那说明已经被最大值干掉了，不进行操作，此时队列中的队头是除下一个窗口的最后一个数组的最大值

               3、实现窗口的添加push() -- 添加元素：因为我们要实现的是单调队列，所以在添加进去前要跟队列的元素进行比较，比待添加的元素要小的时候，就要将值弹出，因为这个队列是单调递减的，所以我们从队列的后面开始进行比较，如果小于就弹出，知道队列中的元素都比待添加的值大，再将元素添加进去

       将单调队列实现好之后我们就可以很好地比较窗口中的最大值了，其中getMaxNum()方法不用说，一直保持队头是最大值。

       poll()更多的是判断队头是不是上一个窗口的第一个元素，因为队列中要保持只有k个元素，这里有两种极端情况和一种常见情况，下图示例：

push()方法做了比较的事，再加入队列的时候就进行比较，是保持队列窗口单调的关键，下图举一下例：

       上面两张图中基本就将所有情况都包含在内了，图和代码结合起来看更加清楚明了