• 单调队列-滑动窗口


    文章目录

    Question

    给定一个大小为 n≤106
    的数组。

    有一个大小为 k
    滑动窗口,它从数组的最左边移动到最右边。

    你只能在窗口中看到 k
    个数字。

    每次滑动窗口向右移动一个位置。

    以下是一个例子:

    该数组为 [1 3 -1 -3 5 3 6 7],k
    为 3

    窗口位置 最小值 最大值
    [1 3 -1] -3 5 3 6 7 -1 3
    1 [3 -1 -3] 5 3 6 7 -3 3
    1 3 [-1 -3 5] 3 6 7 -3 5
    1 3 -1 [-3 5 3] 6 7 -3 5
    1 3 -1 -3 [5 3 6] 7 3 6
    1 3 -1 -3 5 [3 6 7] 3 7
    你的任务是确定滑动窗口位于每个位置时,窗口中的最大值和最小值。

    输入格式
    输入包含两行。

    第一行包含两个整数 n
    和 k
    ,分别代表数组长度和滑动窗口的长度。

    第二行有 n
    个整数,代表数组的具体数值。

    同行数据之间用空格隔开。

    输出格式
    输出包含两个。

    第一行输出,从左至右,每个位置滑动窗口中的最小值。

    第二行输出,从左至右,每个位置滑动窗口中的最大值。

    输入样例:
    8 3
    1 3 -1 -3 5 3 6 7
    输出样例:
    -1 -3 -3 -3 3 3
    3 3 5 5 6 7

    Ideas

    Code

    • 暴力
    #include 
    #include 
    #include 
    
    using namespace std;
    const int N = 1e6 + 10;
    int a[N];
    
    int main(){
        int n, k;
        cin >> n >> k;
        for (int i = 0; i < n; i ++){
            cin >> a[i];
        }
        
        for (int i = 0; i + k <= n; i ++){
            int min = a[i];
            for (int j = 1; j < k; j ++){
                if (a[i + j] < min) min = a[i + j];
             }
             cout << min << ' ';
        }
        puts("");
        for (int i = 0; i + k <= n; i ++){
            int max = a[i];
            for (int j = 1; j < k; j ++){
                if (a[i + j] > max) max = a[i + j];
             }
             cout << max << ' ';
        }
        return 0;
       
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 单调队列
    #include 
    #include 
    #include 
    
    using namespace std;
    const int N = 1e6 + 10;
    int a[N], q[N];
    int hh, tt = -1; // 数组模拟队列
    
    int main(){
        int n, k;
        cin >> n >> k;
        
        for (int i = 0; i < n; i ++){
            cin >> a[i];
        }
        
        for (int i = 0; i < n; i ++){
            if (hh <= tt && i - k + 1 > q[hh]) hh ++; // 队列中有元素, 且当前的窗口左区间>队头
            while(hh <= tt && a[q[tt]] >= a[i]) tt --; // 维护单调递增队列
            
            q[++ tt] = i;
            
            if (i >= k - 1) cout << a[q[hh]] << ' ';
        }
        puts("");
        
        hh = 0, tt = -1;
        for (int i = 0; i < n; i ++){
            if (hh <= tt && i - k + 1 > q[hh]) hh ++;
            while(hh <= tt && a[q[tt]] <= a[i]) tt --;
            
            q[++ tt] = i;
            
            if (i >= k - 1) cout << a[q[hh]] << ' ';
        }
        return 0;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
  • 相关阅读:
    Ubuntu 22.04.1 LTS 离线安装Docker
    Go操作MySQL
    Redis源码与设计剖析 -- 9.字符串对象
    全网最全抖音运营攻略
    视频会议解决方案-最新全套文件
    Python之元组&&集合基础操作
    golang 线程 定时器 --chatGPT
    编程随笔-Java | 02.File类常用API
    什么是MySQL?MySql的学习之路是怎样的
    看三年的CRUD程序员如何解决数据库死锁的
  • 原文地址:https://blog.csdn.net/qq_49821869/article/details/133749511