精华内容
下载资源
问答
  • 2022-02-20 11:42:36

    算法简介
    滑动窗口,顾名思义,就是有一个大小可变的窗口,左右两端方向一致的向前滑动(右端固定,左端滑动;左端固定,右端滑动)。

    可以想象成队列,一端在push元素,另一端在pop元素,如下所示:
    假设有数组[a b c d e f g h]
    一个大小为3的滑动窗口在其上滑动,则有:
    [a b c]
      [b c d]
        [c d e]
          [d e f]
            [e f g]
              [f g h]
    适用范围
    1、一般是字符串或者列表
    2、一般是要求最值(最大长度,最短长度等等)或者子序列
    算法思想
    1、在序列中使用双指针中的左右指针技巧,初始化 left = right = 0,把索引闭区间 [left, right] 称为一个窗口。
    2、先不断地增加 right 指针扩大窗口 [left, right],直到窗口中的序列符合要求。
    3、此时,停止增加 right,转而不断增加 left 指针缩小窗口 [left, right],直到窗口中的序列不再符合要求。同时,每次增加 left前,都要更新一轮结果。
    4、重复第 2 和第 3 步,直到 right 到达序列的尽头。

    思路其实很简单:第 2 步相当于在寻找一个可行解,然后第 3 步在优化这个可行解,最终找到最优解。左右指针轮流前进,窗口大小增增减减,窗口不断向右滑动。

    以上内容来自:

    作者:tunsuy
    链接:https://leetcode-cn.com/circle/article/9gcJBk/
    来源:力扣(LeetCode)

    又名尺取法,根据不同类型可以有窗口大小固定的,和可变的。滑动窗口算法可以用以解决数组/字符串的子元素问题,它可以将嵌套的循环问题,转换为单循环问题,降低时间复杂度。

    简单实例:

    洛谷P1614

    ​​​​​爱与愁的心痛

    输入格式

    第一行有两个用空格隔开的整数,分别代表 n和 m。

    第 2 到第 (n + 1)行,每行一个整数,第 (i + 1) 行的整数代表第i件事的值 ​。

    输出格式

    输出一行一个整数,表示连续 m个值的和的最小值是多少。

    输入输出样例

    输入 

    8  3

    1

    4

    7

    3

    1

    2

    4

    3
    输出
    6

    #include <bits/stdc++.h>
    using namespace std;
    int main()
    {
        int m,n,t;
        cin>>n>>m;
        vector<int>s;
        for(int i=0;i<n;i++)
        {
            cin>>t;
            s.push_back(t);
        }
        int minsum=0;
        for(int i=0;i<m;i++)
        {
            minsum+=s[i];
        }
        int winsum=minsum;
        for(int i=m;i<n;i++)
        {
            winsum+=s[i]-s[i-m];
            if(minsum>winsum)
                minsum=winsum;        
        }
        cout<<minsum;
        return 0;
    }
    更多相关内容
  • 滑动窗口算法的分布式窗口限速的Golang实现。 安装$ go get -u github.com/RussellLuo/slidingwindow设计slidewindow是t slidewindowow的一种实现,Golang是滑动窗口算法的一种实现,用于分布式速率限制。 安装$ go ...
  • 滑动窗口算法

    千次阅读 2022-04-04 15:27:50
    滑动窗口是计算机语言中重要的算法之一,主要用于处理连续的数组数据或者字符串数据,常用来提取数据中的子数组或者子串。 当然无论什么算法只要愿意去做和理解都不会太难。 提示:以下是本篇文章正文内容,下面...

    滑动窗口:


    滑动窗口的作用

    滑动窗口是计算机语言中重要的算法之一,主要用于处理连续的数组数据或者字符串数据,常用来提取数据中的子数组或者子串。
    

    当然无论什么算法只要愿意去做和理解都不会太难,下面我就用JAVA语言来演示一下算法原型案例。
    提示:以下是本篇文章正文内容,下面案例可供参考

    一、滑动窗口案例-1

    209.长度最短的子数组

    class Solution {
        	public static int minSubArrayLen(int target, int[] nums) {
    		int num = 0;	//计算子数组的累计和
    		int min = nums.length;	//长度值赋初值
            boolean b=false;	//判断长度值是否改变过
    		Queue<Integer> m = new LinkedList<Integer>();
    		//定义队列,在我的理解中,队列是最能体现出滑动窗口特点的数据结构之一
    		int i;
    		for (i = 0; i < nums.length; i++) {
    			if (num >= target) {
    				min = Math.min(min, m.size());//求当前值和之前值中的最小值
                    b=true;
    				break;
    			}
    			m.offer(nums[i]);	//向队列m中添加数据nums[i]
    			num += nums[i];
    		} // 设置滑动窗口的初始长度
    //第一个循环用于初始化滑动窗口的长度此时我们就已经有了一个长度为m.size()的窗口了
    		while (num >= target || i < nums.length) { // 				如果已经将nums中的数据全都放入队列m中后,就可以进行筛选。
    			if (num >= target) {
    				min = Math.min(min, m.size());
                    b=true;
    				num -= m.poll();
    //此时m中存放值的总和已经超过了目标值target,此时就突出了滑动窗口的特点了,此时我们的窗口已经满足的滑动的条件,如果现在num的值超过目标值就将前面先进入队列m的值踢出,就相当于窗口就向后移动了一步
    			} else {
    				num += nums[i];
    				m.offer(nums[i++]);
    			//如果此时不满足num>=target条件就继续向后延伸,向队列m中推入之后的值加到num中。
    			}
    
    		}
    		if (!b)
    			return 0;
    		return min;
    	}
    }
    

    经过这道题应该能大概明白滑动窗口是个什么东西了,就是先定义一组满足条件的数据使其成为一个窗口,再通过滑动这个窗口来满足我们需要的条件,我们处理的数据就是窗口中的数据

    二、滑动窗户案例-2

    567.字符串的排序

    class Solution {
        public boolean checkInclusion(String s1, String s2) {
        int len1=s1.length(),len2=s2.length();
        char[] str1=s1.toCharArray();	//将字符串转为字符数组更好处理数据
        char[] str2=s2.toCharArray();
        int[] a1= new int[26]; 	//定义长度为26的整数数组a1、a2记录26个字母出现的次数
        int[] a2= new int[26];
        if(len1>len2)	//如果子串比主串长,直接退出
            return false;
        for(int i=0;i<26;i++)
            {a1[i]=0;
             a2[i]=0;}
        for(int i=0;i<len1;i++)
            {
                a1[str1[i]-'a']++;
                a2[str2[i]-'a']++;
            }
         //统计前len1个字母出现个数
         //此时也相当于创建了一个长度为len1的窗口
        if(Arrays.equals(a1,a2))
            return true;
         //用Arrays.equals(x1,x2)判断两个数组是否完全相等
        for(int i=len1;i<len2;i++)
        {a2[str2[i]-'a']++;
        a2[str2[i-len1]-'a']--;
        //此时开始通过上面两行代码进行滑动:
        	//a2[str2[i]-'a']++;   将新假如的字符转换成对应下标进行加减
        	//a2[str2[i-len1]-'a']--;  从头开始减去之前的数据
       if(Arrays.equals(a1,a2))//每次滑动都判断是否相等
            return true;}
        return false;
        }
    }
    
    
    
    

    案例原型

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    在这里插入图片描述
    在这里插入图片描述

    在这里插入图片描述

    总结

    滑动窗口的使用方式:

    • 根据题目要求先设置窗口大小
    • 设置滑动范围
    • 滑动窗口
    • 退出

    自我感觉滑动窗口的方式和队列的运行方式有很多相似的地方,就比如:

    • 根据题意设置队列大小 ------- 设置窗口大小
    • 队列先进先出的运行模式 ------- 窗口中的数据先进先出

    但滑动窗口的特点是窗口可以是静态也可以是动态。

    • 案例一就是动态窗口,当选择值已经不能再改变的时候就可以通过动态改变窗口中的数据来判断是否是我们需要的值。
    • 案例二则是静态窗口,因为每道题的题意原因所以不能妄下定论说每个知识点的必然性。

    滑动窗口的特点在于处理连续的数据多用于取 子数组和子串 子数组和子串的共同点在于他们的 连续性 都是连续处理的数据,所以滑动窗口算法将会判断处理完所有的数据之后才会得出答案。 因为滑动窗口算法需要判断完所有数据之后得出最优解,所以判断条件大多都是以数组或者字符串长度来定。

    当理解了理论之后刷题自然是必不可少的:LeetCode力扣.滑动窗口专题

    展开全文
  • MATALB可调用的图像滑动窗口算法,用mex编译后可调用。返回滑动窗口得到的图片块样本。
  • 从零开始手写vio- 第5节滑动窗口第5节滑动窗口算法实践
  • JavaScript滑动窗口算法

    千次阅读 2022-04-09 20:13:50
    JavaScript滑动窗口算法1 思想2 代码 1 思想 在力扣上刷题时经常可以看到这样的题,求XXX的子串、子数组、子序列等等,这类题一般使用滑动窗口来解决。本篇文章的思路学习了bilibili的up主红桃A士。 情况一:寻找...

    JavaScript滑动窗口算法

    1 思想

    在力扣上刷题时经常可以看到这样的题,求XXX的子串、子数组、子序列等等,这类题一般使用滑动窗口来解决。本篇文章的思路学习了bilibili的up主红桃A士。

    情况一:寻找最长的

    ①初始化左右指针left和right,左右指针之间的内容就是窗口,定义一个变量result记录当前的滑动窗口的结果,定义一个变量bestResult记录当前滑动窗口下的最优结果
    ②right要向右逐位滑动循环
    ③每次滑动后,记录当前滑动的结果。如果当前的结果符合条件,则更新最优的结果,然后right要继续向右滑动;如果当前的结果不符合条件,那么要让left逐步收缩
    ④当right到达结尾时停止滑动

    初始化left,right,result,bestResult
    while (右指针没有到结尾) {
        窗口扩大,加入right对应元素,更新当前result
        while (result不满足要求) {
            窗口缩小,移除left对应元素,left右移
        }
        更新最优结果bestResult
        right++;
    }
    返回bestResult
    

    情况二:寻找最短的

    ①初始化左右指针left和right,左右指针之间的内容就是窗口,定义一个变量result记录当前的滑动窗口的结果,定义一个变量bestResult记录当前滑动窗口下的最优结果
    ②right要向右逐位滑动循环
    ③每次滑动后,记录当前滑动的结果。如果当前的结果符合条件,则更新最优的结果,然后right要继续向右滑动;如果当前的结果不符合条件,那么要让left逐步收缩
    ④当right到达结尾时停止滑动

    初始化left,right,result,bestResult
    while (右指针没有到结尾) {
        窗口扩大,加入right对应元素,更新当前result
        while (result不满足要求) {
        	更新最优结果bestResult
            窗口缩小,移除left对应元素,left右移
        }
        right++;
    }
    返回bestResult
    

    2 代码

    下面以力扣的两道题来说明两种情况。

    1、寻找最长的

    力扣3. 无重复字符的最长子串

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

    示例 1:
    输入: s = “abcabcbb”
    输出: 3
    解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。

    示例 2:
    输入: s = “bbbbb”
    输出: 1
    解释: 因为无重复字符的最长子串是 “b”,所以其长度为 1。

    示例 3:
    输入: s = “pwwkew”
    输出: 3
    解释: 因为无重复字符的最长子串是 “wke”,所以其长度为 3。

    var lengthOfLongestSubstring = function (s) {
        let left = right = len = maxLen = 0;
        let arr = []; // 记录当前滑动窗口包含的字符
    
        // 当右指针指向字符串最右边时停止循环
        while (right < s.length) {
            if (arr.includes(s[right])) { // 如果滑动窗口中的字符串包含了右指针指向的元素
                // 当arr中不包含右指针指向的字符,停止循环
                while (arr.includes(s[right])) {
                    arr.shift(); // 删除最左边的元素
                    len--; // 更新当前的长度
                    left++; // 左指针右移
                }
                // 循环结束后,arr中不包含右指针指向的元素
                arr.push(s[right]);
                len++;
                right++;
            } else { // 如果滑动窗口中的字符串不包含右指针指向的元素
                arr.push(s[right]);
                len++; // 更新当前状态
                if (len > maxLen) { // 如果当前长度大于记录的最大长度,则更新最大长度
                    maxLen = len;
                }
                right++;
            }
        }
        return maxLen;
    };
    

    2、寻找最短的

    力扣209. 长度最小的子数组

    给定一个含有 n 个正整数的数组和一个正整数 target 。找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。

    示例 1:
    输入:target = 7, nums = [2,3,1,2,4,3]
    输出:2
    解释:子数组 [4,3] 是该条件下的长度最小的子数组。

    示例 2:
    输入:target = 4, nums = [1,4,4]
    输出:1

    示例 3:
    输入:target = 11, nums = [1,1,1,1,1,1,1,1]
    输出:0

    var minSubArrayLen = function (target, nums) {
        let left = 0, right = 0; // 定义左右指针
        let result = 0; // 记录当前滑动窗口的值
        let bestResult = 0; // 记录最优的值
        while (right < nums.length) { // 右指针移动到最右边《结束循环
            result = result + nums[right]; // 记录当期滑动窗口的值
            while (result >= target) {
                // 如果当前的最好的结果大于左右指针之间的长度,更新最优结果
                if (right - left + 1 < bestResult || bestResult == 0) {
                    bestResult = right - left + 1;
                }
                // 将左指针向右移,并且左指针的值从当前结果里面减掉
                result -= nums[left];
                left++;
            }
            right++; // 向右滑动窗口
        }
        return bestResult;
    };
    
    展开全文
  • 限流之滑动窗口算法实战

    千次阅读 2022-01-09 12:57:36
    滑动窗口算法弥补了计数器算法的不足。滑动窗口算法把间隔时间划分成更小的粒度,当更小粒度的时间间隔过去后,把过去的间隔请求数减掉,再补充一个空的时间间隔。 如下图所示,把1分钟划分为10个更小的时间间隔,...

    一 算法

    滑动窗口算法弥补了计数器算法的不足。滑动窗口算法把间隔时间划分成更小的粒度,当更小粒度的时间间隔过去后,把过去的间隔请求数减掉,再补充一个空的时间间隔。

    如下图所示,把1分钟划分为10个更小的时间间隔,每6s为一个间隔。

    1 一个时间窗口为1分钟,滑动窗口分成10个格子,每个格子6秒。

    2 每过6秒,滑动窗口向右移动1个格子。

    3 每个格子都有独立的计数器。

    4 如果时间窗口内所有的计数器之和超过了限流阀值,则触发限流操作。

    如下图所示,滑动窗口算法比计数器算法控制得更精细。

    用户在0:59 时刻发送了100个请求,第10个格子的计数器增加100,下一秒的时候时间窗口向右移动1格,这时再来100个请求就超过了阈值,不会处理这100个请求,这样就避免了计数器场景出现的问题。

    滑动窗口设置得越精细,限流的效果越好,但滑动窗口的时间间隔(小格子)多了,存储的空间也会增加。

    二 需求

    1 设计一个滑动窗口,窗口有10个格子,每个格子10秒,每隔10秒移动一格。

    2 装满所有格子的时间为 10 * 10 = 100 秒。也就是说时间窗口是 100 秒。

    3 从100秒开始,开始滑动,新请求数开始覆盖老请求数。

    三 代码

    package currentLimit;
    
    import java.util.Date;
    import java.util.Random;
    
    /**
    * @className: CounterLimit
    * @description: 滑动窗口算法
    * @date: 2022/1/8
    * @author: cakin
    */
    public class SlideWindowLimit {
        // 滑动窗口大小
        static final int size = 10;
        // 滑动窗口数组,每移动一个格子,更新对应数据项的值
        static int window[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
        // 理解为移动窗口中正在计数的格子
        static int curId = 0;
        // 记录上次统计时间
        static Date lastDate = new Date();
        // 当前窗口计数总和
        static int counter = 0;
    
        /**
         * 功能描述:模拟一次请求是否限流
         *
         * @return true:限流 false;不限流
         * @author 贝医
         * @date 2022/1/8
         * @description:
         */
        static boolean slideWindowLimit() {
            // 获取当前时间
            Date now = new Date();
            // 当前时间同上次记录时间的间隔,单位为秒
            long time = (now.getTime() - lastDate.getTime()) / 1000;
            // 按照新的移动窗口进行计数
            if (time >= 10) {
                // 当前计数格子的下一个格子将被清掉重写
                curId++;
                curId = curId % size;
                int newCurId = curId;
                // 下一个格子将被清掉,总数据减掉
                counter = counter - window[newCurId];
                // 新格子设置为1
                window[newCurId] = 1;
                // 记录滑动的时间
                lastDate = now;
            } else {
                // 当前计数的格子
                ++window[curId];
            }
            ++counter;
            return counter >= 1000;
        }
    
        // 测试方法
        public static void main(String[] args) {
            for (; ; ) {
                // 模拟一秒
                try {
                    Thread.sleep(1000);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                Random random = new Random();
                int i = random.nextInt(3);
                // 模拟1秒内请求8次
                if (i == 1) {
                    for (int j = 0; j < 8; j++) {
                        if (slideWindowLimit()) {
                            System.out.println("限流了" + counter);
                        } else {
                            System.out.println("没限流" + counter);
                        }
                    }
                } else if (i == 2) { // 模拟1秒内请求9次
                    for (int j = 0; j < 9; j++) {
                        if (slideWindowLimit()) {
                            System.out.println("限流了" + counter);
                        } else {
                            System.out.println("没限流" + counter);
                        }
                    }
                } else { // 模拟1秒内请求10次
                    for (int j = 0; j < 10; j++) {
                        if (slideWindowLimit()) {
                            System.out.println("限流了" + counter);
                        } else {
                            System.out.println("没限流" + counter);
                        }
                    }
                }
            }
        }
    }

    四 测试

    五 说明

    记录滑动窗口中的请求数。滑动窗口中的请求数控制在 1000以内。滑动窗口能记录100秒的请求,所以如果每秒请求不超过10,不会限流。测试用例也是这样设计的,每秒模拟发送的请求为8次,9次,10次。从测试结果来看,符合预期。

    展开全文
  • 说起滑动窗口这个算法思路,很多人会感到头秃,这个算法技巧的思路非常简单,就是维护一个窗口,不断滑动,然后更新答案,那么如何向窗口中添加新元素,如何缩小窗口,在窗口滑动的哪个阶段更新结果这些都是要考虑的...
  • 滑动窗口 滑动窗口概念不仅存在于数据链路层,也存在于传输层,两者有不同的协议,但基本原理是相近的。其中一个重要区别是,一个是针对于帧的传送,另一个是字节数据的传送。 滑动窗口(Sliding window)是...
  • C++滑动窗口算法

    2021-02-05 10:11:17
    滑动窗口算法在一个特定大小的字符串或数组上进行操作,而不在整个字符串和数组上操作,这样就降低了问题的复杂度,从而也达到降低了循环的嵌套深度。 如下题 给你两个长度相同的字符串,s 和 t。 将 s 中的第 i 个...
  • 滑动窗口算法实现 C#

    2012-11-30 10:01:41
    The sliding window algorithm 的过程是,随着窗口的增大有效的近似轨迹也随之增长,直到近似轨迹与原始归轨迹的误差值超过指定的误差范围。
  • 滑动窗口算法简单总结

    千次阅读 2021-02-19 13:49:32
    滑动窗口
  • 最后抽象出一个简单的滑动窗口算法框架。 LeetCode 上至少有 9 道题目可以用此方法高效解决。但是有几道是 VIP 题目,有几道题目虽不难但太复杂,所以本文只选择点赞最高,较为经典的,最能够讲明白的三道题来讲解。...
  • java基础-滑动窗口算法

    千次阅读 2021-09-11 23:33:32
    } } 滑动窗口是基于暴力解法的优化,其强大的思想被应用在很多地方,比如我们熟知的网关限流算法,其中有滑动窗口算法滑动窗口算法有个缺点,就是临界的问题,现在都采用令牌桶算法来限流,感兴趣的小伙伴可以...
  • 这里写目录标题Sentinel的限流原理滑动时间窗口算法 Sentinel的限流原理 限流效果,对应有DefaultController快速失败 WarmUpController慢启动(令牌桶算法) RateLimiterController(漏桶算法) 滑动时间窗口算法 ...
  • 滑动窗口算法总结

    2021-03-11 14:40:01
    昨天晚上,闲来无事去学校acm队训练机房呆了一会,太受刺激了,大一的把我摁在地上摩擦,属实很拉,学习了一个滑动窗口算法。唉,现在算法刚开课,之前自己也学过一段时间,但刷体很少。以后晚上得经常去跟着他们...
  • 滑动窗口算法(C语言版讲解)

    千次阅读 2021-06-07 17:10:02
    滑动窗口算法(C语言版讲解) 滑动窗口算法主要用于解决字符串查找对应排序的题型。 算法的基本思路 1.辅助算法 :快慢指针 由于要运用快慢指针的思想,这里读者需要先了解快慢指针。 typedef struct node{ int ...
  • C++滑动窗口算法理解与实例

    千次阅读 2020-11-19 18:28:52
    C++滑动窗口算法目的实例实例1题目描述解题思路代码实例2题目描述解题思路代码总结 目的 如何将嵌套for循环在少数问题中转换为单个for循环,从而减少了时间的复杂性。 实例 实例1 题目描述 给一组大小为n的整数数组...
  • 【C语言】滑动窗口算法

    千次阅读 多人点赞 2020-05-16 23:59:09
    1.滑动窗口的思想: 它是一个运行在一个大数组上的子列表,该数组是一个底层元素集合。假设有数组 [a b c d e f g h ],一个大小为 3 的 滑动窗口 在其上滑动,则有: [a b c]  [b c d]    [c d e]      [d e ...
  • 在力扣常用解题法中,我们常常会看到这些: 滑动窗口 双指针 快慢指针/ 链表题目 原地链表翻转 区间合并 ...而偏偏是最常用的,也排在首位的滑动窗口算法,却并不为人熟知,什么是滑动窗口算法呢?? .
  • 这几天在leetcode刷题,经常遇到可以使用滑动窗口来解决的题目,所以找...在这篇文章, 我会从一道题目入手,先讲解暴力算法, 再到滑动窗口, 然后分析为什么他是对的,最后还会给出滑动窗口算法的一个模板、使用场景、以及
  • 我写了套框架,把滑动窗口算法变成了默写题

    千次阅读 多人点赞 2020-04-22 07:30:00
    点击上方蓝字设为星标东哥带你手把手撕力扣~作者:labuladong 公众号:labuladong若已授权白名单也必须保留以上来源信息我有预感本文要火,所以先罗列一下我们号的所有算法套...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 62,003
精华内容 24,801
关键字:

滑动窗口算法