滑动窗口合集

1.Leetcode1004

题目:给定一个由若干 01 组成的数组 A,我们最多可以将 K 个值从 0 变成 1 。返回仅包含 1 的最长(连续)子数组的长度。

输入:A = [1,1,1,0,0,0,1,1,1,1,0], K = 2
输出:6
解释:
[1,1,1,0,0,1,1,1,1,1,1]
最长的子数组长度为 6。

思路

利用滑动窗口维护一个0的个数小于K的区间,每次r向右移动一步,判断当前0的数量是否大于K,如果大于就l向右移动,直到0的数量小于=K

class Solution {
    public int longestOnes(int[] A, int K) {
        int n=A.length;
        int l=0,r=0;
        int zs=0;
        int ans=-1;
        while(r<n){
            if(A[r]==0) zs++;
            while(zs>K){
                if(A[l++]==0) --zs;
            }
            ans=Math.max(ans,r-l+1);
            r++;
        }
        return ans;
    }
}

2.leetcode424

题目:给你一个仅由大写英文字母组成的字符串,你可以将任意位置上的字符替换成另外的字符,总共可最多替换 k 次。在执行上述操作后,找到包含重复字母的最长子串的长度。

输入:s = "AABABBA", k = 1
输出:4
解释:
将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。
子串 "BBBB" 有最长重复字母, 答案为 4。

class Solution {
public:
    int  num[26];
    int characterReplacement(string s, int k) {
        int n=s.size();
        int l=0,r=0;
        int maxn=0;
        while(r<n){
            num[s[r]-'A']++;
            maxn=max(maxn,num[s[r]-'A']);
            if(r-l+1-maxn>k){
                num[s[l]-'A']--;
                l++;
            }
            r++;
        }        
        return n-l;
    }
};

3.LeetCode1438

1.滑动窗口维护区间,当区间满足条件r++,不满足条件让l=r再将l向左移,直到不满足条件

class Solution {
public:
    int longestSubarray(vector<int>& nums, int limit) {
        deque<int> queMax, queMin;
        int n = nums.size();
        int left = 0, right = 0;
        int ret = 0;
        while (right < n) {
            while (!queMax.empty() && queMax.back() < nums[right]) {
                queMax.pop_back();
            }
            while (!queMin.empty() && queMin.back() > nums[right]) {
                queMin.pop_back();
            }
            queMax.push_back(nums[right]);
            queMin.push_back(nums[right]);
            while (!queMax.empty() && !queMin.empty() && queMax.front() - queMin.front() > limit) {
                if (nums[left] == queMin.front()) {
                    queMin.pop_front();
                }
                if (nums[left] == queMax.front()) {
                    queMax.pop_front();
                }
                left++;
            }
            ret = max(ret, right - left + 1);
            right++;
        }
        return ret;
    }
};

//单调队列

class Solution {
public:
    int longestSubarray(vector<int>& nums, int limit) {
        deque<int> queMax, queMin;
        int n = nums.size();
        int left = 0, right = 0;
        int ret = 0;
        while (right < n) {
            while (!queMax.empty() && queMax.back() < nums[right]) {
                queMax.pop_back();
            }
            while (!queMin.empty() && queMin.back() > nums[right]) {
                queMin.pop_back();
            }
            queMax.push_back(nums[right]);
            queMin.push_back(nums[right]);
            while (!queMax.empty() && !queMin3#.empty() && queMax.front() - queMin.front() > limit) {
                if (nums[left] == queMin.front()) {
                    queMin.pop_front();
                }
                if (nums[left] == queMax.front()) {
                    queMax.pop_front();
                }
                left++;
            }
            ret = max(ret, right - left + 1);
            right++;
        }
        return ret;
    }
};

4.LeetCode1052.爱生气的书店老板

题目:

今天,书店老板有一家店打算试营业 customers.length 分钟。每分钟都有一些顾客(customers[i])会进入书店,所有这些顾客都会在那一分钟结束后离开。

在某些时候,书店老板会生气。 如果书店老板在第 i 分钟生气,那么 grumpy[i] = 1,否则 grumpy[i] = 0。 当书店老板生气时,那一分钟的顾客就会不满意,不生气则他们是满意的。

书店老板知道一个秘密技巧,能抑制自己的情绪,可以让自己连续 X 分钟不生气,但却只能使用一次。

请你返回这一天营业下来,最多有多少客户能够感到满意的数量。

示例:

输入:customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], X = 3
输出:16
解释:
书店老板在最后 3 分钟保持冷静。
感到满意的最大客户数量 = 1 + 1 + 1 + 1 + 7 + 5 = 16.

提示:

  • 1 <= X <= customers.length == grumpy.length <= 20000
  • 0 <= customers[i] <= 1000
  • 0 <= grumpy[i] <= 1

滑动窗口:先把所有满足的叠加起来,再在长度为K的滑动窗口内取最大满意数

class Solution {
    public int maxSatisfied(int[] customers, int[] grumpy, int X) {
            int n=customers.length;
            int total=0,temp=0,ans=0,maxn=0;
            int l=0,r=0;
            while(r<n){
                total+=(1-grumpy[r])*customers[r];
                ans+=grumpy[r]*customers[r];
                maxn=Math.max(ans,maxn);
                r++;
                if(r-l+1>X) ans-=grumpy[l]*customers[l++];   
            }
            return maxn+total;
    }
}


滑动窗口o(n)写法

class Solution {
    public int maxSatisfied(int[] customers, int[] grumpy, int X) {
        int total = 0;
        int n = customers.length;
        for (int i = 0; i < n; i++) {
            if (grumpy[i] == 0) {
                total += customers[i];
            }
        }
        int increase = 0;
        for (int i = 0; i < X; i++) {
            increase += customers[i] * grumpy[i];
        }
        int maxIncrease = increase;
        for (int i = X; i < n; i++) {
            increase = increase - customers[i - X] * grumpy[i - X] + customers[i] * grumpy[i];
            maxIncrease = Math.max(maxIncrease, increase);
        }
        return total + maxIncrease;
    }
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×