剑指offer题目:(hard)

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

解法批注：简直是妙蛙种子吃着妙脆角进了米奇妙妙屋，妙到家了(^_^)

剑指 Offer 59 - I. 滑动窗口的最大值

我们先看什么是单调的双向队列，双向队列大家都知道，既能在头部进行插入、删除操作，也能在尾部进行插入删除操作，而所谓的单调，就是我们人为规定从队列的头部到尾部，所存储的元素是依次递减（或依次递增）的。如下所示：

头部 尾部
—————————————
| 5 3 2 1 0 -1 |
—————————————
由大 → 到小
也就是说，我们维护一个单调的双向队列，窗口在每次滑动的时候，我就从队列头部取当前窗口中的最大值，每次窗口新进来一个元素的时候，我就将它与队列中的元素进行大小比较：

  • 如果刚刚进来的元素比队列的尾部元素大，那么先将队列尾部的元素弹出，然后把刚刚进来的元素添到队列的尾部；
  • 如果刚刚进来的元素比队列的尾部元素小，那么把刚刚进来的元素直接添到队列的尾部即可。

下面通过图示进行说明。

分析
添加元素
在不规定窗口大小的前提下，我们先看看如何将新元素添加到单调的双向队列中。假如有5、4、1、2、6要进入单调的双向队列，首先让索引为0的元素5进入，由于之前队列是空的，所以5直接进去即可，如下所示：

头部 尾部
—————————————
| 5 |
| ↑ |
| 0 |
—————————————
大 小
此时，索引1位置上的4要进队列，则需要比较队列尾部与4的大小关系。由于5是大于4的，并且4从尾部进去以后能够满足从头到尾、从大到小的规定，所以我们让4进去即可，如下所示：

头部 尾部
—————————————
| 5 4 |
| ↑ ↑ |
| 0 1 |
—————————————
大 小
然后，索引2位置上的元素1也想要进去，根据我们的规定，让它直接进入就好了，如下所示：

头部 尾部
—————————————
| 5 4 1 |
| ↑ ↑ ↑ |
| 0 1 2 |
—————————————
大 小
然后，索引3位置上的元素2想要进去，此时，由于尾部的元素1是小于元素2的，2进去以后不满足从大到小的规定，所以让1从尾部出来，直接丢掉它，然后再让元素2从尾部进入，如下所示：

头部 尾部
—————————————
| 5 4 2 |
| ↑ ↑ ↑ |
| 0 1 3 |
—————————————
大 小
你可以看到，对于上面的这些过程，每次在元素进来之前，我们都可以通过LinkedList.peekFirst()操作来获取队列的头部，也就是整个队列的最大值，同时也是当前窗口的最大值。

每进入一个元素我就可以取最大值，每进入一个元素我就可以取最大值，每进入一个元素我就可以取最大值。（这句话说了三遍~）

因此，我就是通过这种既能从头部进出，又能从尾部进出的结构，来维持窗口的最大值的。

好了，现在还剩下索引为4的元素6想要进入队列，我们发现6比队列中任何一个元素都要大，所以我们将队列中的所有元素都弹出，然后只让6进入，如下所示：

头部 尾部
—————————————
| 6 |
| ↑ |
| 4 |
—————————————
大 小
此时，窗口中的最大值就是6了。要注意一点的是：如果此时又来了一个索引为5的元素6想要进入队列中，则我们需要将之前的索引为4的元素6进行弹出，让新来的6进入，此时就变成了如下所示：

头部 尾部
—————————————
| 6 |
| ↑ |
| 5 |
—————————————
大 小
为什么在元素相等的情况下，也要更新元素呢？

这是因为窗口是每次向右进行滑动的，每次进入到窗口中的值都有可能是当前窗口中最大的值，我们将相同的值进行更换，其实是为了更新它的索引。这样在窗口进行滑动的时候，每次的最大值都是新的，就能保持最大。

删除元素
不妨假设以下场景，窗口大小是 2，之前窗口中包含5和4，但是此时已经来到了4、1元素，队列中的情况也如下所示：

元素： 5 [4 1] 2
索引： 0 1 2 3

头部 尾部
—————————————
| 5 4 1 |
| ↑ ↑ ↑ |
| 0 1 2 |
—————————————
大 小
由于元素5已经被滑动窗口略过了，所以我们应将队列中的最大值，也就是5弹出，让4成为当前窗口新的最大值，如下所示：

头部 尾部
—————————————
| 4 1 |
| ↑ ↑ |
| 1 2 |
—————————————
大 小
总结
总之，整个流程看起来比较繁琐，不过你可以用一个具体的例子，按照下面的代码走一遍，就能知道整个流程是怎么样运行的。

作者：SirCarol
链接：https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/solution/java-dan-diao-shuang-xiang-lian-biao-hua-tu-xiang-/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。