滑动窗口解题模板

问题

Leetcode 1208

解题模板

#include <bits/stdc++.h>

using namespace std;

class Solution
{
public:
    int equalSubstring(string s, string t, int maxCost)
    {
        int sum = 0;
        int ans = 0;
        int st = 0;
        int ed = 0;
        // 循环不变式：在每一次循环之前都面对一个新的窗口[st,ed]
        // 终止：ed到达末尾，此时只能收缩st，窗口只会越变越小，因此为结束条件
        while(ed < s.size())
        {
            // 更新窗口
            sum += abs(s[ed] - t[ed]);
            // 判断窗口是否正确，如果不正确，并且还能收缩，那么就收缩
            while(sum > maxCost && st <= ed)
            {
                sum -= abs(s[st] - t[st]);
                st++;
            }
            // 更新记录
            ans = max(ans,ed - st + 1);
            // 创建下一个窗口
            ed++;
        }
        return ans;
    }
};