Sliding Window
滑动窗口跟CNN里面的卷积计算操作很像。具体来说就是给定一组数据,然后从前到后扫描所有的数据,每次取出一段连续的区间,可以是等长的也可以是变长的。
滑动窗口问题一般可以从三个角度来考虑:
窗口扩张
一般就是right向右移动一位
窗口收缩
需要思考什么时候left右移。一般是非目标字符。有时候是常规的收缩,有时候是带优化性质的收缩。
寻找最值(目标情形)
根据具体情况构造。比如求最长/最短,就用fmin,fmax来迭代。
模板
int left = 0;int right = 0;while(right < n){if(需要收缩){left++;// left = right;}if(目标情形){ret = fmax(ret, right-left+1);}right++;}
例题
剑指 Offer 59 - I. 滑动窗口的最大值
3. 无重复字符的最长子串
76. 最小覆盖子串
239. 滑动窗口最大值
395. 至少有K个重复字符的最长子串
424. 替换后的最长重复字符
567. 字符串的排列
978. 最长湍流子数组
1438. 绝对差不超过限制的最长连续子数组