【题解】滑动窗口（单调队列）

题目描述：

输入：

输入包含两行。

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

...