滑动窗口通用思路#

1func solve(){
2    
3    // windows是用来维护随着滑动窗口变化的而产生变化的值或者数据结构
4    var windows any
5
6    // 答案
7    var ans any
8
9    // 定义窗口左右边界
10    l,r := 0,0
11    for r=0;r<n;r++ {
12        // 右边界进入给windows带来的影响
13        changeR(windows)
14        // 如果窗口达到定长，可以移动左边界
15        if r-l+1==k {
16            // 当当前滑动窗口合法时
17            if checkValid() {
18                // 计算ans
19                ans = max(ans,sum)
20            }
21            
22            // 左边界移除给windows带来的影响
23            changeL(windows)
24
25            // 左边界向右移动
26            l++
27        }
28    }
29    return ans
30}

1func solve() {
2    l,r := 0,0
3
4    // windows是用来维护随着滑动窗口变化的而产生变化的值或者数据结构
5    var windows any
6
7    // 答案
8    var ans any
9
10    for r=0;r<n;r++ {
11        // 右边界进入给windows带来的影响
12        changeR(windows)
13
14        // checkInvalidAboutL表示检查当前滑动窗口是否不合法，如果随着l的右移，不合法会转变为合法，则该条件应该被写上；
15        // 否则随着l的右移，不合法不会转变为合法，甚至情况更糟，则该条件不该被写上
16        
17        // checkCouldBetterAboutL表示检查当前滑动窗口维护的值是否可以更优
18        // 如果满足某些条件时,l右移会更优，该条件应该被写上
19        // 否则如果l右移是否更优并不确定，则不该被写上
20
21        // 所以 checkInvalidAboutL 和 checkCouldBetterAboutL 不一定都需要写
22        // 这里只是写出了包含他们都可以写的情况
23        for l<=r && (checkInvalidAboutL() || checkCouldBetterAboutL()) {
24            // 左边界移除给windows带来的影响
25            changeL(windows)
26
27            // 左边界向右移动
28            l++
29        }
30
31        // 该窗口合法
32        if checkValid() {
33            // 统计答案
34            ans = getAns(ans)
35        }
36
37    }
38
39}