©2020-2024 ioDraw All rights reserved,
Privacy Policy
滑动窗口
滑动窗口有俩种：定窗口和不定窗口。滑动窗口说白了就是双指针的运用。
定窗口说明是一个特定窗口大小，通常用来解决相邻的元素，最大值，最小值。
不定窗口说的是，先由右指针去找到第一个能够符合题意的位置，记录该答案，再将左指针往后移动至不满足条件为止，此时可以刷新答案，再由右指针继续去寻找。
定窗口求最值：这个需要借助双向队列去完成。我举一个列子求项链3个元素最大值：
我们首先判断head指针是否需要出队，需要出队是说明窗口不能装下这些元素了。
继而去找，我们要的是最大值，如果当前元素值小于tai指针代指的值，直接接下去即可，但如果是大于，就要去从后往前找比他大的数字后面存储该值，并且放弃掉当前元素大于que队列里面的元素。
小于：
出队的情况
另外输出的话，我们知道当i>2时我们就需要输出队头元素，队头元素永远是当前窗口最大的元素。
所以答案是
不定窗口：
通常解决某个子串或者子序列最长或者最短。
我们还是举列子：
A串：abcddeft
B串：bd
求包含B串的A串最短子串。
首先移动j到符合题意：
发现满足题意，于是存储下来：
移动i 到 不满足题意，需要在这个过程中刷新值
就解决了，类似的问题也还是一样。