滑动窗口★★★

解决哪类问题

:::success 求解连续区间最值 :::

代码模板

求最大窗口大小（for版本）

int  maxLen = 0; // 窗口最大值
int sum = 0; // 当前状态
for(int l = 0, r = 0; r < arr.length; r++) {
    sum += arr[r]; // 根据加入右指针更新状态
    if (sum <= maxCost) { // 满足约束
        maxLen = Math.max(maxLen, r - l + 1); // 更新窗口最大值
    } else { // 不满足约束
        sum -= arr[l]; // 根据去除左指针更新状态
        l++; // 左指针右移
    }
}
return maxLen;

求最大窗口大小（双while版本1）

while(r < n){
    UPDATE STATE(r)
    while(WRONG){
        UPDATE STATE(l)
        l++
    }
    MAXORMIN(ans)
    r++
}

求最大窗口大小（双while版本2）

int l = 0, r = 0, sum = 0, maxLen = 0; // 初始化左右指针，状态值，窗口大小
while (r < n) { // 右指针不越界
    sum += arr[r]; // 根据加入右指针更新状态
    while(sum > maxCost) { // 不符合约束条件
        sum -= arr[l]; // 根据去除左指针更新状态
        l++; // 左指针右移
    }
    maxLen = Math.max(maxLen, r - l + 1); // 更新窗口最大值
    r++; // 右指针右移
}
return maxLen;

求最大窗口大小（双while版本3）

int l = 0, r = 0, sum = 0, maxLen = 0; // 初始化左右指针，状态值，窗口大小
while (r < n) { // 右指针不越界
    sum += arr[r]; // 根据加入右指针更新状态
    r++; // 右指针右移
    while(sum > maxCost) { // 不符合约束条件
        sum -= arr[l]; // 根据去除左指针更新状态
        l++; // 左指针右移
    }
    maxLen = Math.max(maxLen, r - l); // 更新窗口最大值（注意区别）
}
return maxLen;

窗口不需要减小

int l = 0, r = 0, sum = 0;
for(; r < n; r++) {
    if(sum + arr[r] > maxCost) { // 不满足约束，左右指针同时移动
        sum += arr[r] - arr[l]; // 更新状态
        l++;
    } else { // 满足约束，右指针移动
        sum += arr[r]; // 更新状态
    }
}
return r - l;

滑动窗口复杂样板

public String minWindow(String s, String t) {
    int left = 0, right = 0; // 滑动窗口前后指针
    int min = Integer.MAX_VALUE; // 最小子串的长度
    int start = 0, end = 0; // 最小子串的左右位置
    int count = 0; // 相同字符的个数
    Map<Character, Integer> tMap = new HashMap<>(); // target串的字符计数（目标）
    Map<Character, Integer> sMap = new HashMap<>(); // source串的字符计数（窗口）
    // 初始化target串的字符计数
    for (int i = 0; i < t.length(); ++i) {
        tMap.put(t.charAt(i), tMap.getOrDefault(t.charAt(i), 0) + 1);
    }
    while (right < s.length()) {
        char c = s.charAt(right);
        // 更新窗口状态
        if (tMap.containsKey(c)) { // 是所求字符
            sMap.put(c, sMap.getOrDefault(c, 0) + 1); // 存字符进窗口
            if (tMap.get(c).compareTo(sMap.get(c)) == 0) { // 看是不是该字符达标
                count++;
            }
        }
        right++; // 右滑动扩大
        while (count == tMap.size()) {
            // 满足条件，更新最值
            if (min > right - left) {
                end = right;
                start = left;
                min = right - left;
            }
            char d = s.charAt(left);
            // 更新窗口状态
            if (tMap.containsKey(d)) {
                sMap.put(d, sMap.get(d) - 1);
                if (tMap.get(d) > sMap.get(d)) {
                    count--;
                }
            }
            left++; //左滑动缩小
        }
    }
    return min == Integer.MIN_VALUE ? "" : s.substring(start, end);
}

复杂度

O(n)

运用思想

无

例题