滑动窗口小trick

小灰灰 2024-03-30 08:40 70阅读 0赞

滑动窗口用于维护定长区间信息

时间复杂度为O(n)

应用1：

维护区间最值：

#include <stdio.h>
    #include <queue>
    using namespace std;
    const int mxn=1e6+10;
    int n,k;
    int a[mxn],mi[mxn],mx[mxn];//mi存窗口最小值，mx存窗口最大值
    deque<int> q,q2;
    int main(){
        scanf("%d%d",&n,&k);
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        for(int i=1;i<=n;i++){
            while(!q.empty()&&i-q.front()+1>k) q.pop_front();
            while(!q.empty()&&a[q.back()]>=a[i]) q.pop_back();
            q.push_back(i);
            mi[i]=a[q.front()];
        }
        for(int i=k;i<=n;i++) printf("%d%c",mi[i],i==n?'\n':' ');
    
    
        for(int i=1;i<=n;i++){
            while(!q2.empty()&&i-q2.front()+1>k) q2.pop_front();
            while(!q2.empty()&&a[q2.back()]<=a[i]) q2.pop_back();
            q2.push_back(i);
            mx[i]=a[q2.front()];
        }
        for(int i=k;i<=n;i++) printf("%d%c",mx[i],i==n?'\n':' ');
        return 0;
    }

可以发现滑动窗口是这样的：

![fae2d60a18a44ebebb10465b5688f392.png][]

比如说我们需要维护\[L,R\]的值

首先，我们取消维护不属于区间内的值（橙色部分）

然后将R部分加入区间

**然后这个区间就成型了 ，**可以去利用这个区间的信息来维护其他的信息了

因此就调用滑动窗口的模板就行了

[fae2d60a18a44ebebb10465b5688f392.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/2f188d3f7a18437494cb58dbd450f8d9.png

发表评论取消回复

表情：

评论列表（有 0 条评论，70人围观）

还没有评论，来说两句吧...

相关阅读

相关滑动窗口小trick

滑动窗口用于维护定长区间信息时间复杂度为O(n) 应用1：维护区间最值： include <stdio.h> include <queue>

小灰灰/ 2024年03月30日 08:40/ 0 赞/ 71 阅读

相关【算法小课堂】滑动窗口

滑动窗口 ![在这里插入图片描述][68694b06872046779b9583c7ea02acc2.png_pic_center] 基本概念：滑动窗口本质是双

深藏阁楼爱情的钟/ 2024年03月01日 08:06/ 0 赞/ 68 阅读

相关 TCP 滑动窗口

滑动窗口机制解析： 1.窗口机制滑动窗口协议的基本原理就是在任意时刻，发送方都维持了一个连续的允许发送的帧的序号，称为发送窗口；同时，接收方也维持了一个连续的允许接收的

素颜马尾好姑娘i/ 2022年10月06日 12:54/ 0 赞/ 204 阅读

相关 LeetCode 滑动窗口最大值【滑动窗口】

1 滑动窗口最大值给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移

秒速五厘米/ 2022年09月10日 11:26/ 0 赞/ 216 阅读

相关 leetcode滑动窗口

1. 无重复字符的最长子串给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。输入: s = “abcabcbb” 输出: 3 采用滑动窗口搜

Bertha 。/ 2022年09月04日 09:53/ 0 赞/ 254 阅读

相关滑动窗口机制

[滑动窗口][Link 1] (1).窗口机制滑动窗口协议的基本原理就是在任意时刻，发送方都维持了一个连续的允许发送的帧的序号，称为发送窗口；同时，接收方也维持

迈不过友情╰/ 2022年08月10日 06:26/ 0 赞/ 235 阅读

相关 Unity 滑动窗口

unity 滑动窗口创建一个image 名为Note 在Note下再创建一个image image下创建一个text ![Center][] 调节大小比如N

不念不忘少年蓝@/ 2022年06月14日 01:47/ 0 赞/ 244 阅读

相关 window滑动窗口

spark Streaming提供了滑动窗口操作的支持，从而我们可以对一个滑动窗口内的数据执行计算操作，每次掉落在窗口内的RDD的数据，会被聚合起来执行计算操作，然后生成的RD

╰半橙微兮°/ 2022年05月16日 12:45/ 0 赞/ 250 阅读

相关滑动窗口

①初始态，发送方没有帧发出，发送窗口前后沿相重合。接收方0号窗口打开，等待接收0号帧； ②发送方打开0号窗口，表示已发出0帧但尚确认返回信息。此时接收窗口状态不变； ③发送

喜欢ヅ旅行/ 2022年03月15日 07:12/ 0 赞/ 300 阅读

相关滑动窗口法

给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。示例 1: 输入: "abcabcbb" 输出: 3 解释: 因为无

红太狼/ 2022年02月17日 01:41/ 0 赞/ 242 阅读