精选文章 滑动窗口(单调队列)

滑动窗口(单调队列)

作者:alex1997222 时间: 2020-08-04 02:43:54
alex1997222 2020-08-04 02:43:54

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

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

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

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

以下是一个例子:

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

窗口位置最小值最大值
[1 3 -1] -3 5 3 6 7-13
1 [3 -1 -3] 5 3 6 7-33
1 3 [-1 -3 5] 3 6 7-35
1 3 -1 [-3 5 3] 6 7-35
1 3 -1 -3 [5 3 6] 736
1 3 -1 -3 5 [3 6 7]37

您的任务是确定滑动窗口位于每个位置时,窗口中的最大值和最小值。

输入格式

输入包含两行。

第一行包含两个整数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

解题思路:

利用单调队列思想

窗口滑动经过1和3时,并没有破坏队列的单调性,同时也没有凑足三个数字,所以将1和3直接入队

滑动经过-1时,由于1和3都比-1要大,所以将1和3出队,将-1入队,此时由于窗口内有3个元素,所以最小的元素是-1

经过-3时,-3比-1要小,破坏了队列的单调性,所以将-1出队,-3入队

经过5时,将5压入队列(保持单调性),输出队头元素(最小的那一个)

以此类推直到经过最后一个元素

#include 
using namespace std;
const int N = 1000010;
int q[N],a[N],hh = 0,tt = -1;
int n,k;

int main(){
    cin >> n >> k;
    for(int i = 0;i < n;++i) scanf("%d",&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) printf("%d ",a[q[hh]]);
        
    }
    
    cout< q[hh]) hh++;
        while(hh <= tt && a[q[tt]] <= a[i]) tt--;
        q[++tt] = i;
        if(i >= k - 1) printf("%d ",a[q[hh]]);
    }
    
    return 0;
}

 

勿删,copyright占位
分享文章到微博
分享文章到朋友圈

上一篇:C语言/C++编程学习:送给考计算机二级的同学:公共基础知识总结!

下一篇:2020前端面试专题整理

您可能感兴趣

  • C++面试题总结(二)

    51. 引用与指针有什么区别? 答 : 1) 引用必须被初始化,指针不必。 2) 引用初始化以后不能被改变,指针可以改变所指的对象。 3) 不存在指向空值的引用,但是存在指向空值的指针。 52. 描述实时系统的基本特性 答 、在特定时间内完成特定的任务,实时性与可靠性。 54. 全局变量和局部变量在内存中是否有区别?如果有,是什么区别? 答 、全局变量储存在静态数据区,局部变量在堆栈中。 5...

  • 新职业教育的三节课,凭什么做到今天这样

    历时7天、翻遍15个平台渠道、访谈25位参与课程的从业者、挖掘了136条推文的标题和内容,我们得到了12500字的拆解。可以点击右上角☝:收藏、分享、在看,不用担心看一半,找不到文章。 本文信息公开来源:三节课官方公众号、虎嗅网、36氪、深网、东方财富网、新榜、知乎、简书、增长黑盒、短书··· 我们认为,这可能比任何官方复盘更能诠释:「三节课」是如何在3年内,做到互联网职业教育(Almost...

  • ORLACE数据库管理-resource manager资源管理优化

    假如管理一下具有如下问题的产品数据库: 后台批作业占用了大量的资源,将会阻碍了其他要同时运行的更重要的作业。 如要调度大型作业,但不能预计它们何时才能完成。 作业的优先次序没有得到区分,而致使重要的作业不能预先完成。 某些用户使用过量的CPU时间,从而导致总体资源缺乏,这时,不得不结束其会话。 有些用户在操作中使用非常高的并行度,这会降低系统的整体性能。 所有这些问题都源于DBA不能够在竞争...

  • Python很难学吗?网友直呼:原来学霸是这样的,那我也可以!

    很多人觉得Python难学,学着学着,就从入门学到放弃了,那学霸们,是如何来学习Python的呢?学霸优秀且异于常人,当然是有原因的,包括学习方法,资料,自律等等的因素,小编觉得这其中最重要的,莫过于他们手中的学习清单了吧,今天,一向宠粉的小编,给小伙伴们整理了学霸们的Python学习清单 Python是以简单易学著名的,自学的话是完全可以学会的。 除此之外呢,小编还给大家准备了一份大礼,P...

  • SpringCloud(1):SpringCloud介绍

    1.微服务介绍 1.1 什么是微服务? 微服务是一种架构风格,也是一种服务; 微服务的颗粒比较小,一个大型复杂软件应用由多个微服务组成,比如Netflix目前由500多个的微服务组成; 它采用UNIX设计的哲学,每种服务只做一件事,是一种松耦合的能够被独立开发和部署的无状态化服务(独立扩展、升级和可替换)。 1.2 微服务架构图 1.3 微服务的好处 技术异构性:在一个由多个服务相互协作的系...

  • 目标检测经典论文——R-CNN论文翻译:Rich feature hierarchies for accurate object detection and semantic segmentation

    Rich feature hierarchies for accurate object detection and semantic segmentation——Tech report (v5) 用于精确物体定位和语义分割的丰富特征层次结构——技术报告(第5版) Ross Girshick Jeff Donahue Trevor Darrell Jitendra Malik UC Berk...

  • 字节跳动面经整理

    1. 操作系统: 进程和线程介绍; 进程或线程死锁介绍; 多进程,多线程的并发执行带来的问题-死锁 死锁是指多个进程(线程)在执行过程中,由于竞争资源或者彼此通信而造成的一种阻塞的现象(互相挂起等待),若无外力他们都将无法推进下去。 银行家算法 了解活锁吗?(没听过) 操作系统中的堆和栈; 栈(操作系统):由编译器自动分配释放,存放函数的参数值,局部变量的值等。其操作方式类似于数据结构中栈,...

  • 软件测试面试1--软件测试基础理论(持续更新中...)

    1.软件测试工程师的素质: 良好的沟通和表达能力 具有怀疑与破坏的精神 扎实的软件测试基础知识 缜密的业务逻辑分析能力 处在用户的角度进行换位思考 足够的耐心、细心、信心、责任心 积极乐观向上的心态和团队协作能力 要有严谨、敢于承担责任、稳重的做事风格 善于自我总结、自我督促和不断学习的能 2.软件的分类: 软件 = 程序 + 数据 + 文档。   按照功能划分:     系统软件:如操作系...

华为云40多款云服务产品0元试用活动

免费套餐,马上领取!
CSDN

CSDN

中国开发者社区CSDN (Chinese Software Developer Network) 创立于1999年,致力为中国开发者提供知识传播、在线学习、职业发展等全生命周期服务。