C - 滑动窗口 /【模板】单调队列

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

Description

有一个长为 n 的序列 a,以及一个大小为 k 的窗口。现在这个从左边开始向右滑动,每次滑动一个单位,求出每次滑动后窗口中的最大值和最小值。

例如:

The array is [1,3,−1,−3,5,3,6,7] and k=3。

C - 滑动窗口 /【模板】单调队列,c语言,算法,开发语言

Input

输入一共有两行,第一行有两个正整数 n,k。
第二行 n 个整数,表示序列 a

Output

输出共两行,第一行为每次窗口滑动的最小值
第二行为每次窗口滑动的最大值

Sample 1

Inputcopy Outputcopy
8 3
1 3 -1 -3 5 3 6 7
-1 -3 -3 -3 3 3
3 3 5 5 6 7

Hint

【数据范围】
对于50% 的数据,1≤n≤10^5;
对于100% 的数据,1≤k≤n≤10^6,ai​∈[−231,231)。

 

#include<iostream>
using namespace std;
const int N = 1e6 + 10;
int a[N], maxq[N], minq[N];
int n, m;

//h是队头,用于输出答案;t是队尾,用于加入和删除元素
//注意:对头为左,队尾为右,队头只出,队尾可出可进;因此若队内有元素,则h<=t
//max队内的元素因保持单调递减的性质,加入的不是元素值,而是元素所在数组a中的下标
void maxfind() {
	int h = 0, t = -1;

	for (int i = 1; i <= n; i++)
	{
		if (h <= t && maxq[h] <= i - m) h++;    //不在当前滑动窗口的元素删除
		while (h <= t && a[i] >= a[maxq[t]]) t--; //a[i]为当前元素,若当前元素大于队尾的元素,则需要删除,时其满足单调递减的性质
		maxq[++t] = i;   //加入新元素的下标
		if(i>=m) cout << a[maxq[h]] << " ";//输出结果
	}
}
//原理同上
void minfind() {
	int h = 0, t = -1;

	for (int i = 1; i <= n; i++)
	{
		if (h <= t && minq[h] <= i - m) h++;
		while (h <= t && a[i] <= a[minq[t]]) t--;
		minq[++t] = i;
		if(i>=m) cout << a[minq[h]] << " ";
	}
}

int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> a[i];
	minfind();
	cout << endl;
	maxfind();
	return 0;
}

 单调队列模板(滑动窗口)_滑动窗口 /【模板】单调队列_胡牧之.的博客-CSDN博客文章来源地址https://www.toymoban.com/news/detail-688359.html

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

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

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

相关文章

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

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

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

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

    2024年02月13日
    浏览(49)
  • 算法模板之单调栈和单调队列图文详解

    🌈个人主页: 聆风吟 🔥系列专栏: 算法模板、数据结构 🔖少年有梦不应止于心动,更要付诸行动。      💬 hello! 各位铁子们大家好哇,今天作者给大家带来了单调栈和单调队列的算法模板讲解,让我们一起加油进步。      📚 系列专栏:本期文章收录在《算法

    2024年02月02日
    浏览(45)
  • LeetCode 239.滑动窗口的最大值 Hot100 单调栈

    给你一个整数数组  nums ,有一个大小为  k   的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的  k  个数字。滑动窗口每次只向右移动一位。 返回  滑动窗口中的最大值  。 示例 1: 示例 2: 提示: 1 = nums.length = 105 -104 = nums[i] = 104 1 = k = num

    2024年02月20日
    浏览(50)
  • 【map】【滑动窗口】【优先队列】LeetCode480滑动窗口中位数

    动态规划 多源路径 字典树 LeetCode2977:转换字符串的最小成本 C++算法:滑动窗口总结 map 优先队列 中位数是有序序列最中间的那个数。如果序列的长度是偶数,则没有最中间的数;此时中位数是最中间的两个数的平均数。 例如: [2,3,4],中位数是 3 [2,3],中位数是 (2 + 3) / 2 =

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

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

    2024年02月06日
    浏览(50)
  • 算法设计-单调队列

    这个东西我弄得还不是很明白,所以先放一篇博客:https://www.cnblogs.com/I-Love-You-520/p/13454305.html ​ 单调队列说的就是博客中提到的场景,可以说解决的是 固定长度,多次查询一段的最值 (其实就是slice window的意思),这种如果是朴素算法的话,因为查一段序列的最值的时间复

    2023年04月08日
    浏览(31)
  • 力扣日记10.30-【栈与队列篇】滑动窗口最大值

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

    2024年02月06日
    浏览(46)
  • 【二】一起算法---队列:STL queue、手写循环队列、双端队列和单调队列、优先队列

    纸上得来终觉浅,绝知此事要躬行。大家好!我是霜淮子,欢迎订阅我的专栏《算法系列》。 学习经典算法和经典代码,建立算法思维;大量编码让代码成为我们大脑的一部分。 ⭐️已更系列  1、基础数据结构        1.1、链表➡传送门        1.2、队列➡本章 专栏直达

    2023年04月08日
    浏览(53)
  • 【leetcode:1944. 队列中可以看到的人数】单调栈算法及其相关问题

    1944. 队列中可以看到的人数 有  n  个人排成一个队列, 从左到右  编号为  0  到  n - 1  。给你以一个整数数组  heights  ,每个整数  互不相同 , heights[i]  表示第  i  个人的高度。 一个人能  看到  他右边另一个人的条件是这两人之间的所有人都比他们两人  矮  。更

    2024年01月25日
    浏览(34)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包