当前位置：首页 > article >正文

【跟着灵神刷力扣】定长滑动窗口

article 2025/3/25 12:12:41

檐角炊烟软暮光，云层裂隙漏斜阳。
新茧裹着旧伤结，老门推开陈酒香；
烛火飘摇明灭处，闷雷沉在青砖墙。
蜻蜓点破春潭影，一池星碎待风狂。

- 个人定长滑窗解题模板
- §1.1 基础非会员题目
- - 1456. 定长子串中元音的最大数目
  - 643. 子数组最大平均数 I
  - 1343. 大小为 K 且平均值大于等于阈值的子数组数目
  - 2090. 半径为 k 的子数组平均值
  - 2379. 得到 K 个黑块的最少涂色次数
  - 2841. 几乎唯一子数组的最大和
  - 2461. 长度为 K 子数组中的最大和
  - 1423. 可获得的最大点数
  - 1052. 爱生气的书店老板
  - 1652. 拆炸弹

个人定长滑窗解题模板

初始化窗口及累积变量
确定窗口长度 k，处理非法输入（如 k > n 直接返回）。
我的习惯性写法：

		int right;
        for(right=0;right<k;++right)
        {
            ……维护条件
        }

这样的写法有两点好处：一是right可以留存而非在for的局部结束后被销毁，用于下一次在k+1到l的遍历；二，也是最重要的，始终是后面的遍历成为[,)左闭右开区间，遍历后面时left始终等于right-k，不用考虑加减1的情况

滑动窗口更新累积值
从索引 k 开始遍历，每次右移窗口：
添加新元素：当前右指针 right 对应值加入累积。
移除旧元素：左边界元素（索引 right - k）从累积中扣除。
实时更新最终结果
每次滑动后立即计算当前窗口状态，更新结果变量。

§1.1 基础非会员题目

1456. 定长子串中元音的最大数目

1456. 定长子串中元音的最大数目
个人题解：

class Solution {
public:
    bool isVowel(char c)
    {
        return c=='a'||c=='e'||c=='i'||c=='o'||c=='u';
    }
    int maxVowels(string s, int k) 
    {
        int l=s.size(),maxx=0,cnt=0;
        int right;
        for(right=0;right<k;++right)
        {
            if(isVowel(s[right])) cnt++;
        }
        maxx=cnt;
        for(;right<l;++right)
        {
            if(isVowel(s[right])) cnt++;
            if(isVowel(s[right-k])) cnt--;
            maxx=max(maxx,cnt);
        }
        return maxx;
    }
};

643. 子数组最大平均数 I

643. 子数组最大平均数 I
个人题解：

class Solution {
public:
    double findMaxAverage(vector<int>& nums, int k) 
    {
        int l=nums.size();
        double sum=0,maxx=0;
        int right;
        for(right=0;right<k;++right)
        {
            sum+=nums[right];
        }  
        maxx=sum/k;
        for(;right<l;++right)
        {
            sum+=nums[right];
            sum-=nums[right-k];
            double avr=sum/k;
            maxx=max(avr,maxx);
        }  
        return maxx;
    }
};

1343. 大小为 K 且平均值大于等于阈值的子数组数目

1343. 大小为 K 且平均值大于等于阈值的子数组数目
个人题解：

class Solution {
public:
    int numOfSubarrays(vector<int>& arr, int k, int threshold) 
    {
        int l=arr.size(),cnt=0;
        double sum=0,hold=double(threshold);
        int right;
        for(right=0;right<k;++right)
        {
            sum+=arr[right];
        }    
        if(sum/k>=hold) cnt++;
        for(;right<l;++right)
        {
            sum+=arr[right];
            sum-=arr[right-k];
            if(sum/k>=hold) cnt++;
        }
        return cnt;
    }
};

2090. 半径为 k 的子数组平均值

2090. 半径为 k 的子数组平均值
个人题解：

class Solution {
public:
    vector<int> getAverages(vector<int>& nums, int k) 
    {
        int n=nums.size();
        long long sum=0;
        vector<int> avgs(n,-1);
        for(int right=0;right<n;++right)
        {
            if(right<2*k) 
            {
                sum+=nums[right];
            }else
            {
                sum+=nums[right];
                avgs[right-k]=sum/(2*k+1);
                sum-=nums[right-2*k];
            }
        }
        return avgs;
    }
};

2379. 得到 K 个黑块的最少涂色次数

2379. 得到 K 个黑块的最少涂色次数
个人题解：

class Solution {
public:
    int minimumRecolors(string blocks, int k) 
    {
        int l=blocks.size(),cnt=0,minn=0;
        int right;
        for(right=0;right<k;++right) if(blocks[right]=='W') cnt++;
        minn=cnt;
        for(;right<l;++right)
        {
            if(blocks[right]=='W') cnt++;
            if(blocks[right-k]=='W') cnt--;
            minn=min(minn,cnt);
        }
        return minn;
    }
};

2841. 几乎唯一子数组的最大和

2841. 几乎唯一子数组的最大和
个人题解：

class Solution {
public:
    long long maxSum(vector<int>& nums, int m, int k) 
    {
        unordered_map<int,int> cnt;
        int l=nums.size(),judge=0;
        long long sum=0,ans=0;
        int right;
        for(right=0;right<k;++right) 
        {
            if(cnt[nums[right]]==0) judge++;
            cnt[nums[right]]++;
            sum+=nums[right];
        } 
        if(judge>=m) ans=sum;

        for(;right<l;++right)
        {
            if(--cnt[nums[right-k]]==0) judge--;
            sum-=nums[right-k];

            if(cnt[nums[right]]++==0) judge++;
            sum+=nums[right];

            if(judge>=m) ans=max(ans,sum);
        }
        return ans;
    }
};

2461. 长度为 K 子数组中的最大和

2461. 长度为 K 子数组中的最大和
个人题解：

class Solution {
public:
    long long maximumSubarraySum(vector<int>& nums, int k) 
    {
        unordered_map<int,int> cnt;
        int l=nums.size(),judge=0;
        long long sum=0,ans=0;
        int right;
        for(right=0;right<k;++right)
        {
            if(cnt[nums[right]]++==0) judge++;
            sum+=nums[right];
        }
        if(judge==k) ans=sum;

        for(;right<l;++right)
        {
            if(--cnt[nums[right-k]]==0) judge--;
            sum-=nums[right-k];

            if(cnt[nums[right]]++==0) judge++;
            sum+=nums[right];

            if(judge==k) ans=max(ans,sum);
        }
        return ans;
    }
};

1423. 可获得的最大点数

1423. 可获得的最大点数
个人题解：

class Solution {
public:
    int maxScore(vector<int>& cardPoints, int k) 
    {
        vector<int> new_cardPoints(2*k);
        auto it=new_cardPoints.begin();
        it=copy(cardPoints.end()-k,cardPoints.end(),it);
        it=copy(cardPoints.begin(),cardPoints.begin()+k,it);
        int sum=accumulate(new_cardPoints.begin(),new_cardPoints.begin()+k,0);
        int ans=sum;
        for(int right=k;right<2*k;++right)
        {
            sum+=new_cardPoints[right];
            sum-=new_cardPoints[right-k];
            ans=max(ans,sum);
        }
        return ans;
    }
};

1052. 爱生气的书店老板

1052. 爱生气的书店老板
个人题解：

class Solution {
public:
    int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int minutes) 
    {
        int n=customers.size();
        int ans=accumulate(customers.begin(),customers.end(),0);
        int right=0,sum=0,total_mud=0;
        for(;right<minutes;++right) if(grumpy[right]) sum+=customers[right],total_mud+=customers[right];
        int maxx=sum;
        for(;right<n;++right)
        {
            if(grumpy[right]) sum+=customers[right],total_mud+=customers[right];
            if(grumpy[right-minutes]) sum-=customers[right-minutes];
            maxx=max(sum,maxx);
        }
        return ans-(total_mud-maxx);
    }
};

1652. 拆炸弹

1652. 拆炸弹
个人题解：

class Solution {
public:
    vector<int> decrypt(vector<int>& code, int k) 
    {
        int l=code.size();
        vector<int> key(l,0);
        if(k>0)
        {
            vector<int> new_code(2*l,0);
            auto it=new_code.begin();
            it=copy(code.begin(),code.end(),it);
            it=copy(code.begin(),code.end(),it);

            int sum=0,right=1;
            for(;right<=k;++right) sum+=new_code[right];

            int left=0;
            key[left++]=sum;
            for(;left<l;++left,++right)
            {
                sum+=new_code[right];
                sum-=new_code[left];//或者是right-k
                key[left]=sum;
            }

        }else if(k<0)
        {
            vector<int> new_code(2*l,0);
            auto it=new_code.begin();
            it=copy(code.end()+k,code.end(),it);
            it=copy(code.begin(),code.end(),it);

            int sum=0,right=0;
            for(;right<-k;++right) sum+=new_code[right];
            int left=0;
            key[left++]=sum;
            for(;left<l;++left,++right)
            {
                sum+=new_code[right];
                sum-=new_code[left-1];//或者是right+k
                key[left]=sum;
            }
        }   
        return key;
    }
};