acgo题库
  • 首页
  • 题库
  • 学习
  • 天梯
  • 备赛

    竞赛

    • CSP-J/S
    • 蓝桥杯

    考级

    • GESP
    • CPA
    • 电子学会考级
  • 竞赛
  • 讨论
  • 团队
  • 商城
登录
注册
题目详情提交记录(0)
  • 题解

    单调队列还是太吃操作了

    userId_undefined
    复仇者_纳西妲厨一位
    秩序白银时空双修者题解仙人
    22阅读
    1回复
    3点赞
  • 单调队列

    题目大意:让我们从左到右,每次扫描k个长度,并找出这段子序列的最大值,依次输出并换行 解法: 一(50pts): 很容易想到一种模拟的方法,用vector存下每次的元素,找出最大值: 代码非常短小,但是这种方只能通过5个点; 因为这道题的数据范围是1≤k≤n≤2×10 ^6,使用暴力枚举,时间复杂度是O(nk),严重超时。 二(100pts): 那有没有一种数据结构能完整解决这道题呢? 首先考虑一种思路:使用一个“数组”并维持此“数组”的单调性,让数组的头是当前子序列的最大值,并向后单调递减,这样可以使数组的尾为当前序列的最小值,实现方法:将序列的下标放进数组之中,从数组的尾插入值,每次检查数组是否为空且新的元素是否大于数组的尾(因为要保持单调性),如果大于那么弹出当前数组的尾,插入新值,接下来,如果当前数组的长度大于k,那么就要输出数组的头并弹出 这个数组的名字就叫单调队列,一般使用deque实现: 时间复杂度O(n),完全可以胜任这道题目

    userId_undefined
    LUCKY_tetooos
    秩序白银快乐小狗
    7阅读
    0回复
    1点赞
暂无数据

提交答案之后,这里将显示提交结果~

首页