滑动窗口

1、无重复字符的最长子串

（1）题目描述

给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。

（2）解题思路

滑动窗口left right，滑动right，用数组flag存储字符right是否在窗口内出现过，其中right为索引。如果出现过，滑动left，直到符合情况。

（3）代码

#include <string.h>
#define MAX(a, b) ((a) > (b) ? a : b)

int lengthOfLongestSubstring(char* s) {

    int flag[128];
    for (int i = 0; i < 128; i++) flag[i] = 0;

    int n = strlen(s);
    int left = 0;
    int right = 0;
    int maxlen = 0;

    while (right < n && left <= right) {
        
        // 窗口内出现过，不断更新left，直到符合情况
        while (flag[(int)s[right]] == 1) {
            flag[(int)s[left]] = 0;
            left++;
            continue;
        }

        flag[(int)s[right]] = 1;

        maxlen = MAX(maxlen, right - left + 1);

        right++;
    }

    return maxlen;
}

2、爱生气的书店老板

（1）题目描述

有一个书店老板，他的书店开了 n 分钟。每分钟都有一些顾客进入这家商店。给定一个长度为 n 的整数数组 customers，其中 customers[i] 是在第 i 分钟开始时进入商店的顾客数量，所有这些顾客在第 i 分钟结束后离开。在某些分钟内，书店老板会生气。如果书店老板在第 i 分钟生气，那么 grumpy[i] = 1，否则 grumpy[i] = 0。当书店老板生气时，那一分钟的顾客就会不满意，若老板不生气则顾客是满意的。书店老板知道一个秘密技巧，能抑制自己的情绪，可以让自己连续 minutes 分钟不生气，但却只能使用一次。请你返回这一天营业下来，最多有多少客户能够感到满意。

（2）解题思路

答案分为固定收益和额外收益两部分，固定收益很简单。对于额外收益，我们先初始化一个窗口，然后不断滑动，遍历所有窗口，得到所有窗口的额外收益最大值即可。

（3）代码

#define MAX(a, b) ((a) > (b) ? a : b)

int maxSatisfied(int* customers, int customersSize, int* grumpy, int grumpySize, int minutes) {
    // 计算固定收益
    int fixed = 0;

    for (int i = 0; i < grumpySize; i++) {
        if (grumpy[i] == 0) fixed += customers[i];
    }

    // 但是目前多了一个参数minutes 那么我们利用滑动窗口计算额外的收益extra_max
    int c_extra = 0;
    for (int i = 0; i < minutes; i++) {
        if (grumpy[i] == 1) c_extra += customers[i];
    }

    // 滑动窗口
    int extra_max = c_extra;
    for (int i = minutes; i < grumpySize; i++) {
        if (grumpy[i] == 1) c_extra += customers[i]; // 推进
        if (grumpy[i-minutes] == 1) c_extra -= customers[i-minutes]; // 收缩

        extra_max = MAX(extra_max, c_extra);
    }

    return fixed + extra_max;
}

3、双指针滑动窗口

（1）题目描述

给定一个二进制数组 nums 和一个整数 k，假设最多可以翻转 k 个 0，则返回执行操作后数组中连续 1 的最大个数。

（2）解题思路

双指针 left、right，right 不断向后移动，直到 k 为 0 时才开始移动 left，期间不断更新答案。

（3）代码

int longestOnes(int* nums, int numsSize, int k) {

    // 初始化
    int left = 0, right = 0;
    int ans = 0;

    // 滑动窗口
    while (right < numsSize) {
        if (nums[right] == 0) k--;

        while (k < 0) {
            if (nums[left] == 0) k++;
            left++;
        }

        int c_ans = right - left + 1;
        if (c_ans > ans) ans = c_ans;

        right++;
    }

    return ans;
}