蓝桥杯学习笔记03-滑动窗口不定长（最长/最大）

题目来源

分享丨【题单】滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环） - 力扣（LeetCode）

不定长滑动窗口

2024. 考试的最大困扰度 - 力扣（LeetCode）

解决：分别处理‘T’和’F‘

class Solution {
public:
    int apartSitu(string answerKey, char target, int k){
        int len = answerKey.length();
        int left=0,right=0;
        int border=k;
        int maxLen=1;
        for(right=0;right<len;right++){
            if(answerKey[right]!=target) border--;
            while(border<0){
                if(answerKey[left]!=target){
                    border+=1;
                }
                left++;
            }
            maxLen = max(maxLen,right-left+1);
        }
        return maxLen;
    }
    int maxConsecutiveAnswers(string answerKey, int k) {
        // 分别处理 'T' 和 'F'：
        // 由于最终目标是最大化连续 'T' 或 'F' 的数量，因此需要分别计算两种情况的最大长度。
        int maxLen=0;
        maxLen = max(maxLen,apartSitu(answerKey,'T',k));
        maxLen = max(maxLen,apartSitu(answerKey,'F',k));
        return maxLen;
    }
};

1838. 最高频元素的频数 - 力扣（LeetCode）

没有想到满足条件的窗口内的都是已经增加到nums[right-1]的值，体现在cost里

class Solution {
public:
    int maxFrequency(vector<int>& nums, int k) {
        int len = nums.size();
        long long cost=0;
        int left=0, right=0;
        int maxLen=1;
        sort(nums.begin(),nums.end());
        for(right=1;right<len;right++){
            int target = nums[right];
            cost += (long long)(target-nums[right-1])*(right-left);
            while(cost >k && right>left){
                //移动左边界
                cost -= (target-nums[left]);
                left++;
            }
            maxLen = max(maxLen,right-left+1);
        }
        return maxLen;
    }
};

注意数据类型cost是long long ,累加的过程也要强转成(long long)

2516. 每种字符至少取 K 个 - 力扣（LeetCode）

窗口在中间，窗口外的每种字符>=k

class Solution {
public:
    int takeCharacters(string s, int k) {
        unordered_map<char,int> charNum;
        for(char c : s){
            charNum[c]++;
        }
        for(char c : {'a','b','c'}){
            if(charNum[c]<k) return -1;
        }
        int left=0,right=0;
        int len = s.length();
        int minLen=len+1, tem=0;
        unordered_map<char,int> windowCnt;
        for(right=0;right<len;right++){
            windowCnt[s[right]]++;
            while((charNum['a']-windowCnt['a']<k ||
                charNum['b']-windowCnt['b']<k ||
                charNum['c']-windowCnt['c']<k)){
                    windowCnt[s[left]]--;
                    left++;
                }
            minLen = min(minLen, len-(right-left+1));
        }
        return minLen==len+1?-1:minLen;
    }
};

2831. 找出最长等值子数组 - 力扣（LeetCode）

1、用unordered_map记录数字的频率。

2、如果窗口内的大小-最大数字的频率>k，就要减小窗口

class Solution {
public:
    int longestEqualSubarray(vector<int>& nums, int k) {
        unordered_map<int,int> numCnt;
        int len = nums.size();
        int left=0, right=0;
        int maxLen=0, maxFeq=0;
        for(right=0;right<len;right++){
            numCnt[nums[right]]++;
            maxFeq = max(maxFeq,numCnt[nums[right]]);
            if((right-left+1)-maxFeq>k){
                numCnt[nums[left]]--;
                left++;
            }
            maxLen = max(maxLen,maxFeq);
        }
        return maxFeq;
    }
};