从左往右滑动窗口，如果一个数组长度为n、窗口大小为w、则一共生产n-w+1的窗口最大值数组
python
min和max复杂度为O(n)，由于w量级不确定，不方便用，复杂度是O(w*(n-w-1))=O(wn)
4，3，5，4，3，3，6，7
依次和前一个比较的话，每一位都得到一个值，
4，4，5，5，4，3，6，7
现在前后比较即可，比较两个等于比较三个
4，4，5，5，5，4，6，7
如果w再增加，
依次再前后对比，有-1
4，4，5，5，5，5，6，7
最后得到一个数组去掉前w-1位就是最后的数组，不过复杂度也有O(nw)
最佳解法时间复杂度为O(n)，应该使每一个位值的单次比较都用到了前w-1位的比较结果
用双端队列存储数组下标，两端都可插入和弹出，遍历到最新的数组下标i后，维护窗口队列更大值的下标，
1、取到i位的值
如果尾部j，大于这个值，就把i加到尾部（i位是相对较小值，但i位值可能是后续窗口的最大值，i肯定要留着，其实队列里面从左往右对应的数是从大到小的，且长度不会超过w、超过w就过期了，弹出了）；
小于等于这个值，就弹出j，依次往前比较（如果i位值更大，完全可以替代前面x位的最大值，就没必要留着了）
直到这个过程结束：i插进去、或是队列空了
2、如果i对应的位数已经满足构成窗口，
队列如果空了，先把i插进去
然后从双端队列先取队头作为窗口最大值，
队头如果没过期，就用它，因为他是最大的；
如果过期了，就弹出，再往后走1位判断
看了好久才懂这个逻辑、脑壳疼
网友评论