滑动窗口

1208. 尽可能使字符串相等

一开始自己也是一遍过，但是发现写的其实不是很好

class Solution {
public:
    int equalSubstring(string s, string t, int maxCost) {
        int len = s.length();
        int left = 0, right = 0;
        int ans = 0;
        while (right < len) {
            int cost = abs(s[right] - t[right]);
            maxCost -= cost;
            if (maxCost < 0) {
                ans = max(ans, right - left);//right是超出maxCost后移动到的位置，所以不用-1
                maxCost += abs(s[left] - t[left]);//因为左边界要右移，记住减去左边界的cost
                ++left;//窗口左边界右移一格
                maxCost += cost;
            } else {
                ++right;//窗口右边界不断右移
            }
        }
        ans = max(ans, right - left);//检查right超过边界后的情况
        return ans;
    }
};

我写的其实窗口有时会变大有时会变小，所以一直都要判断，后来看了别人题解，类似这种滑动窗口题，要保证的就是窗口不能变小。
如果满足条件就变大，如果不满足条件就右移，这样移动到最右端就是要求的长度了。

class Solution {
public:
    int equalSubstring(string s, string t, int maxCost) 
    {
        int left = 0;   // 窗口左边界
        int cost = 0;   // 当前窗口消耗
        // i作为窗口右边界
        for (int i = 0; i < s.size(); i++)
        {
            cost += std::abs(s[i] - t[i]);
            // 如果当前窗口消耗大于总开销，则左边界++，缩减窗口（其实不是缩减窗口，因为每次循环右边界会右移，所以应该算是右移）
            if (cost > maxCost)
            {
                cost -= std::abs(s[left] - t[left]);
                left++;
            }
        }
        return s.size() - left;
    }
};

这种写法就是，如果窗口里的cost满足就不断只右移右边界，使窗口变大。如果cost不满足了，就缩减左边界，循环结束右右边界扩展，相当于右移，如果还不满足就接着右移，直到移动到最右端，然后这时窗口的宽度就是记录的最宽的宽度，直接输出即可。

要么扩大要么平移，这才是滑动窗口的精髓啊

本作品采用《CC 协议》，转载必须注明作者和本文链接