【题解】滑动窗口(单调队列)

题目描述:

 

输入:

输入包含两行。

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

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

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

输出:

输出包含两个。

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

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

样例:

思考理解:

使用数组实现的单调队列解决。维护两个队列,一个最大值、一个最小值。两个操作分开做,过程几乎一样。

将删除冗余元素,维护一个严格单调的队列,则可以用O(1)时间从队头/队尾取出最值。

以最大值为例,我们需要保证队列内部递减,则队头即所求最大值,过程如下:

  1. 队头出队。当队头元素从窗口滑出时,队头元素出队
  2. 队尾入队。a.直接入队:当新元素小于队尾元素时,直接插入队尾。b.先删后插:如果新元素大于对位元素,就删除队尾元素,循环删除直到队空或者遇到一个比自身大的元素。两种删除方式都是为了保持队列内部递减(最小值则保持内部递增)
  3. 满足条件就输出结果。

需要注意的是:

  • 一定先让新元素入队再检查是否输出(即先2后3),因为要输出的结果可能是新插入的元素
  • 队列中存的是原数组的下标,取值时要再套一层,a[ q[ ] ];
  • 用 scanf 和 printf 提高读入数据和输出数据的效率

代码

# include <iostream> using namespace std; const int N = 1000010; int a[N], q[N], hh, tt = -1;  int main() {     int n, k;     cin >> n >> k;     for (int i = 0; i < n; ++ i)     {         scanf("%d", &a[i]);         //队头出队         if (i - k + 1 > q[hh]) ++ hh;         //循环删除直至满足队列严格单调         while (hh <= tt && a[i] <= a[q[tt]]) -- tt;         //插入当前新元素         q[++ tt] = i;         //输出结果         if (i + 1 >= k) printf("%d ", a[q[hh]]);     }     cout << endl;          //同理     hh = 0; tt = -1;     for (int i = 0; i < n; ++ i)     {         if (i - k + 1 > q[hh]) ++ hh;         while (hh <= tt && a[i] >= a[q[tt]]) -- tt;         q[++ tt] = i;         if (i + 1 >= k) printf("%d ", a[q[hh]]);     }      return 0; }            

推荐这些文章:

动态规划-单调队列优化DP

文章目录
AcWing 135. 最大子序和题目题解代码
AcWing 1087. 修剪草坪题目题解代码
旅行商问题题目题解代码

AcW...

[AcWing 154] 滑动窗口

点击查看代码
#include<iostream>

using namespace std;
const int N = 1e6 + 10;
int a[N], q[N];
int main()
{
int n, k;
scanf("%d %d", &n, &k);
for ...

leetcode队列单调栈- 滑动窗口中的最大值

import leetcode4.test.MonotonicQueue;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
<p>给你一个整数数组 <code>nums</code&g...

leetcode单调栈-每日温度

import java.util.Stack;

/**
<p>给定一个整数数组&nbsp;<code>temperatures</code>&nbsp;,表示每天的温度,返回一个数组&nbsp;<code>answer</code>&nbsp;...

使用类做为Dictionary<T,K>的key需什么要求?

问题
<P>&nbsp;</P>

最佳回答
没有要求

...

leetcode单调栈数组-数组去重

import java.util.Stack;

/**
<p>给你一个字符串 <code>s</code> ,请你去除字符串中重复的字母,使得每个字母只出现一次。需保证 <strong>返回结果的字典序最小</strong>(要求不能打乱其他字符的相对位置)。</p&g...

AcWing 1091. 理想的正方形

题目传送门
二维滑动窗口模板,懂得原理后背下来即可
#include <bits/stdc++.h>

using namespace std;
const int N = 1010;
const int INF = 0x3f3f3f3f;

int n, m, k;
int w[N][N];
int row_min[N][...

leetcode单调栈-下一个最大元素

import java.util.Stack;

/**
<p><code>nums1</code>&nbsp;中数字&nbsp;<code>x</code>&nbsp;的 <strong>下一个更大元素</strong> 是指...

单调队列优化DP问题总结

小结:可见合理的使用哨兵可以简化对边界条件的处理
在单调队列中使用哨兵,主要是在第1个枚举到的数,它依赖的滑动窗口此时为空,无法获取到head,那么此时的处理逻辑是什么样呢?
一般来讲从两个方面来考虑:
(1) 是不是窗口长度越界,需要出队首元素?
while (hh <= tt && q[hh] < i ...

专题学习1 - I - 滑动窗口

题意
给一个长度为 N 的数组,一个长为 K 的滑动窗体从最左端移至最右端,你只能看到窗口中的 K 个数,每次窗体向右移动一位,如下图:

窗口位置
最小值
最大值

[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

...

文章标题:【题解】滑动窗口(单调队列)
文章链接:https://www.dianjilingqu.com/3663.html
本文章来源于网络,版权归原作者所有,如果本站文章侵犯了您的权益,请联系我们删除,联系邮箱:saisai#email.cn,感谢支持理解。
THE END
< <上一篇
下一篇>>