Sliding Window[滑动窗口]

程序员文章站 2022-03-30 11:23:36

Sliding Window滑动窗口跟CNN里面的卷积计算操作很像。具体来说就是给定一组数据，然后从前到后扫描所有的数据，每次取出一段连续的区间，可以是等长的也可以是变长的。滑动窗口问题一般可以从三个角度来考虑：窗口扩张一般就是right向右移动一位窗口收缩需要思考什么时候left右移。一般是非目标字符。有时候是常规的收缩，有时候是带优化性质的收缩。寻找最值（目标情形）根据具体情况构造。比如求最长/最短，就用fmin，fmax来迭代。模板int left = 0;int r...

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++;
}