滑动窗口
滑动窗口有俩种:定窗口和不定窗口。滑动窗口说白了就是双指针的运用。
定窗口说明是一个特定窗口大小,通常用来解决相邻的元素,最大值,最小值。
不定窗口说的是,先由右指针去找到第一个能够符合题意的位置,记录该答案,再将左指针往后移动至不满足条件为止,此时可以刷新答案,再由右指针继续去寻找。
定窗口求最值:这个需要借助双向队列去完成。我举一个列子求项链3个元素最大值:
我们首先判断head指针是否需要出队,需要出队是说明窗口不能装下这些元素了。
继而去找,我们要的是最大值,如果当前元素值小于tai指针代指的值,直接接下去即可,但如果是大于,就要去从后往前找比他大的数字后面存储该值,并且放弃掉当前元素大于que队列里面的元素。
![](https://img-blog.csdnimg.cn/dc33eb9951de4c3aa8f7ff19ea0d6a55.png)
小于:
![](https://img-blog.csdnimg.cn/217cc1031a7e4e5f801dfdee2e8f0cd0.png)
出队的情况
![](https://img-blog.csdnimg.cn/4358d77fe2204302a3a1158277678baf.png)
另外输出的话,我们知道当i>2时我们就需要输出队头元素,队头元素永远是当前窗口最大的元素。
所以答案是
![](https://img-blog.csdnimg.cn/642b1b791c614a489d0ddbe0899c8cd1.png)
不定窗口:
通常解决某个子串或者子序列最长或者最短。
我们还是举列子:
A串:abcddeft
B串:bd
求包含B串的A串最短子串。
![](https://img-blog.csdnimg.cn/a3c45c9cbdc04c8a968596d371b0cd32.png)
首先移动j到符合题意:
![](https://img-blog.csdnimg.cn/7b56daeb1d224782be2bd84a7014708a.png)
发现满足题意,于是存储下来:
![](https://img-blog.csdnimg.cn/5eca07fe223743f69708d7ecf1afaf61.png)
移动i 到 不满足题意,需要在这个过程中刷新值
![](https://img-blog.csdnimg.cn/b1580d4481744cd696debc8a86e76f17.png)
就解决了,类似的问题也还是一样。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)