C++ 单调队列 || 单调队列模版题:滑动窗口

这篇具有很好参考价值的文章主要介绍了C++ 单调队列 || 单调队列模版题:滑动窗口。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

给定一个大小为 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

#include <iostream>
#include <cstdio>
using namespace std;

const int N = 10000010;
int q[N], hh, tt = -1;
int n, k;
int a[N];

int main()
{
    scanf("%d%d", &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 ++;
        
        // 保持队列的递增性质,出队元素直到队列为空或者队尾元素大于当前元素 a[i]
        while(hh <= tt && a[q[tt]] >= a[i])
            tt --;
        
        // 入队当前元素下标 i
        q[ ++ tt] = i;
        
        // 输出当前窗口的最小值(队首元素),i 达到窗口大小 k 时开始输出
        if(i >= k - 1)
            printf("%d  ", 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)
            printf("%d ", a[q[hh]]);
    }


    return 0;

}

注意q中存的是下标。文章来源地址https://www.toymoban.com/news/detail-809024.html

到了这里,关于C++ 单调队列 || 单调队列模版题:滑动窗口的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【二叉树】【单调双向队列】LeetCode239:滑动窗口最大值

    map|动态规划|单调栈|LeetCode975:奇偶跳 C++算法:滑动窗口总结 单调双向队列 二叉树 给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 返回 滑动窗口中的最大值 。

    2024年02月04日
    浏览(56)
  • 滑动窗口最大值 | 单调队列解题思路与实现,前 K 个高频元素

    学习LeetCode 239与347题目的解题思路与实现方法,包括单调队列与优先级队列(堆)的应用。掌握滑动窗口的最大值与前K个高频元素的解决方案。

    2024年02月13日
    浏览(49)
  • 力扣刷题-队列-滑动窗口最大值

    给定一个数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 返回滑动窗口中的最大值。 进阶: 在线性时间复杂度内解决此题? 参考:https://www.programmercarl.com/0239.%E6%BB%91%E5%8A

    2024年02月06日
    浏览(51)
  • 力扣日记10.30-【栈与队列篇】滑动窗口最大值

    日期:2023.10.30 参考:代码随想录、力扣 题目描述 难度:困难 给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 返回 滑动窗口中的最大值 。 示例 1: 示例 2:

    2024年02月06日
    浏览(46)
  • 力扣精选算法100题——水果成篮(滑动窗口专题)

    本题链接👉水果成篮 我就按照实例1来进行对这题的理解。 1代表种类类型,这个数组里面有2个种类类型 ps:种类1和种类2 ,只不过种类1是有2个水果,种类2有一个水果,共计3个水果。 本题需要解答:收集水果的最大数目. 但是前提条件: 我们只有2个篮子,每个篮子里只能装

    2024年01月17日
    浏览(42)
  • 每日OJ题_算法_滑动窗口⑧_力扣76. 最小覆盖子串

    目录 力扣76. 最小覆盖子串 解析及代码 76. 最小覆盖子串 - 力扣(LeetCode) 难度 困难 给你一个字符串  s  、一个字符串  t  。返回  s  中涵盖  t  所有字符的最小子串。如果  s  中不存在涵盖  t  所有字符的子串,则返回空字符串  \\\"\\\"  。 注意: 对于  t  中重复字符,

    2024年01月23日
    浏览(41)
  • 力扣精选算法100题——找到字符串中所有字母异位词(滑动窗口专题)

    本题链接👉找到字符串中所有字母异位词 给定2个字符串s和p,找到s中所有p的变位词的字串,就是p是\\\"abc\\\",在s串中找到与p串相等的字串,可以位置不同,但是字母必须相同,比如”bca\\\",\\\"bac\\\"等,都是可以被称之为变位词。最终返回与p串字母相等但排列不同的字符串的初始索引

    2024年01月19日
    浏览(67)
  • Offer必备算法_滑动窗口_八道力扣OJ题详解(由浅到深)

    目录 滑动窗口算法介绍 ①力扣209. 长度最小的子数组 解析及代码 ②力扣3. 无重复字符的最长子串 解析及代码 ③力扣1004. 最大连续1的个数 III 解析及代码 ④力扣1658. 将x减到0的最小操作数 解析及代码 ⑤力扣904. 水果成篮 解析及代码1(使用容器) 解析及代码2(开数组) ⑥

    2024年02月20日
    浏览(47)
  • 每日OJ题_算法_滑动窗口⑦_力扣30. 串联所有单词的子串

    目录 力扣30. 串联所有单词的子串 解析及代码 30. 串联所有单词的子串 - 力扣(LeetCode) 难度 困难 给定一个字符串  s   和一个字符串数组  words 。   words  中所有字符串  长度相同 。   s   中的  串联子串  是指一个包含   words  中所有字符串以任意顺序排列连接起来的

    2024年01月21日
    浏览(45)
  • 每日OJ题_算法_滑动窗口⑥_力扣438. 找到字符串中所有字母异位词

    目录 力扣438. 找到字符串中所有字母异位词 解析及代码1 解析及代码2 438. 找到字符串中所有字母异位词 - 力扣(LeetCode) 难度 中等 给定两个字符串  s  和  p ,找到  s   中所有  p   的  异位词  的子串,返回这些子串的起始索引。不考虑答案输出的顺序。 异位词  指由

    2024年01月24日
    浏览(47)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包