目录一、什么是单调队列二、单调队列解决的问题三、例题解决1. P1886 【模板】单调队列 / 滑动窗口 - 洛谷2. P2251 质量检测 - 洛谷四、总结一、什么是单调队列单调队列顾名思义就是存储的元素要么单调递增要么单调递减的队列。其实就是我们要维护一个单调递增要么单调递减的队列来解决问题。注意这里的队列不是普通的队列他是一个双端队列链接deque - C Reference。二、单调队列解决的问题通过单调队列我们解决的问题是在滑动窗口中寻找最大值或最小值的问题。除此之外它还可以用来优化动态规划的问题以后说。三、例题解决下面我们就来通过两个例题来理解如何使用单调队列的。1. P1886 【模板】单调队列 / 滑动窗口 - 洛谷题目链接P1886 【模板】单调队列 / 滑动窗口 - 洛谷问题内容题目分析这道题就是让我们在一个数组中从前往后遍历每次遍历都在区间 [ i, i k - 1 ] 区间中找到此时这段长度为k区间中的最大值和最小值直到 i k - 1 到达数组末尾。解决思路这道题就是一个经典的关于双端队列的模板题目这里的队列中存储的是元素的下标这里设置下标从1开始。如果我们将队列中存储的值设置为就是元素的值而不是下标则我们可以以示例数组为 [ 3, 1, 15, 10, 7, 2, 5, 14, 14 ] 窗口大小 k 3 那么我们可以来模拟一下这里设置下标从1开始初始时如图所示其中 ret[ i ] 表示以i位置为结尾的窗口中的最大值的值。假设我们要求滑动窗口中的最大值模拟过程如下所示我们需要从左向右遍历每一个元素遇到第1个元素 3 时此时还没有形成长度为 k 的窗口就将 3 入队得遇到第 2 个元素1 时此时仍没有形成长度为 k 的窗口但是需要和前一个队尾元素比较此时队尾元素大于当前元素则需要就将 1 入队因为1可能是后面窗口中的最大值比如如果从1开始此时窗口中是1 -1 -2, 则此时最大值就是 1得可以发现此时队列就呈现出来递减的趋势了。遇到第 3 个元素15 时此时就形成了一个窗口。比较它和队尾元素的大小此时队尾元素小于15所以可以将队尾元素出队这里可以出队的原因是因为15比1大且靠后所以在包含15往后的窗口中的最大值一定是15而不会是1即队尾元素必定不是之后某个窗口中的最大值同理1 从队尾出队后此时队尾为3也小于15所以也要出队此时队列为空就需要将 15 入队所以此时这里的窗口中最大值就是15即完成上述操作后的队头。得遇到第4个元素 10 时此时将窗口右移窗口中的数就是[ 1, 15, 10 ] 。队尾元素15大于10此时就需要将10入队因为10不是当前这个窗口的最大值但也可能是后面摸个窗口中最大值所以此时窗口中的最大值是 15即队头元素的值最后更新结果 ret[ 4 ] 15。得遇到第 5 个元素 7 时此时将窗口右移窗口中的数就是[ 15, 10, 7 ] 。队尾元素10大于7此时就需要将7入队理由同上所以此时窗口中的最大值是 15即队头元素的值最后更新结果 ret[ 5 ] 15。得遇到第 6 个元素 2 时此时将窗口右移窗口中的数就是[ 10, 7, 2 ] 。队尾元素7大于2此时就需要将2入队理由同上此时窗口中的最大值是应该是 10但是此时队头元素还是15因为此时15已经不在窗口中了所以在更新结果前我们还需要判断一下当前队列中的元素是否都在当前窗口中判断方法就是在队列中存下标判断队头和队尾之前的下标范围即可最后更新结果 ret[ 6 ] 10。得遇到第 7 个元素 5 时此时将窗口右移窗口中的数就是[ 7, 2, 5 ] 。队尾元素2小于5此时需要将队尾元素出队因为当前队尾元素小于5那么在之后包含5的所以窗口中的最大值一定会比5大此时小于5的队尾元素就没有用了。当前队列中的数据为[ 10(队头), 7(队尾) ]再判断队尾元素为7大于5此时就将5入队。入队后此时需要判断一下当前队列中的元素是否都在窗口中此时10已经不在窗口中了所以需要在队头出队此时队列中数据就是[ 7(队头), 5(队尾) ] 所以当前窗口中的最大值就是队头元素 7 即 ret[ 7 ] 7。得遇到第 8 个元素 14 时此时将窗口右移窗口中的数就是[ 2, 5, 14 ] 。此时队尾元素 5 小于 14需要队尾出队。出队后此时队尾为 7 也小于 14也出队此时队列为空将 14 入队此时队头为 14 14 也满足在窗口内所以直接更新结果 ret[ i ] 14。得对到第9个元素 14 时此时将窗口右移窗口中的数就是[ 5, 14, 14 ] 。此时队尾元素等于 14 。为了保证 14 这个值在后续窗口中判断窗口合法所以我们需要将 队尾这个相等的 14 扔掉即出队。此时队列中队头为14这是新加入的14下标是9。同时此时队列中元素都在窗口中所以更新结果 ret[ 9 ] 14。得通过上面这个找最大值的模拟过程我们就可以总结出通过双端队列找最大值的思路设双端队列为q注意其中存的是下标数组为 arr窗口大小为 k。从左向右开始遍历所有大小为k的窗口。如果队列为空则将 arr[ i ] 的下标入队。如果队列非空则需要判断若队尾 arr[ q.back() ]小于等于arr[ i ] 则说明队尾元素不是后面某个窗口的最大值了需要从队尾出队即 q.pop_back()若队尾 arr[ q.back() ]大于arr[ i ] 需要将arr[ i ] 的下标入队因为当前 元素 可能是包含自己的之后窗口中的最大值。然后判断窗口合法即当前队列中的元素是否都是当前窗口中的元素则以当前遍历到的元素为结尾的窗口中最大值就是当前队列的队头元素。重复2,3,4步骤即可。所以找最大值时双端队列就是一个呈现递减的队列。同理对于寻找窗口的最小值的思路为如果队列为空则将 arr[ i ] 的下标入队。如果队列非空则需要判断若队尾 arr[ q.back() ]大于等于arr[ i ] 则说明当前元素更小队尾元素就再不是后面某个窗口的最小值了需要从队尾出队即 q.pop_back()若队尾 arr[ q.back() ]小于arr[ i ] 需要将arr[ i ] 的下标入队因为当前 元素 可能是包含自己的之后窗口中的最小值。然后判断窗口合法即当前队列中的元素是否都是当前窗口中的元素则以当前遍历到的元素为结尾的窗口中最大值就是当前队列的队头元素。所以找最小值时双端队列就是一个呈现递增的队列。在这道题中我们不需要将它们的结构都保存起来只需要找到后直接输出即可。最后我们实现一下这道题的代码#include iostream #include deque using namespace std; const int N 1e6 1; int n, k; int arr[N]; int main() { cin n k; for(int i 1; i n; i) cin arr[i]; dequeint q; // 双端队列 - 存下标 // 找最小值 for(int i 1; i n; i) { while(q.size() arr[q.back()] arr[i]) q.pop_back(); // 当前比队尾小则队尾一定不是当前窗口的最小队尾就没用了 // q为空 // arr[i]比队尾大--当前可能是后面某个窗口的最小值 q.push_back(i); // 判断队列中的元素是否都在窗口中 -- 窗口合法检查 if(q.back() - q.front() 1 k) q.pop_front(); // 队头出队 // 输出合法窗口的结果 if(i k) cout arr[q.front()] ; } cout endl; q.clear(); // 清空队列 // 找最大值 for(int i 1; i n; i) { while(q.size() arr[q.back()] arr[i]) q.pop_back(); // 当前比队尾大则队尾一定不是当前窗口的最大队尾就没用了 q.push_back(i); if(q.back() - q.front() 1 k) q.pop_front(); if(i k) cout arr[q.front()] ; } return 0; }2. P2251 质量检测 - 洛谷题目链接P2251 质量检测 - 洛谷问题内容解决方法这道题就可以转化为在一个分值数组 a 中寻找以 m 长度大小的一段区间中分值的最小值也就是以 i 为结尾的满足窗口大小为 m 的区间中数值的最小值。所以这就是一个单调队列寻找最小值的应用题直接使用单调队列模拟即可。实现代码为#include iostream #include deque using namespace std; const int N 1e5 10; int n, m; int a[N]; int main() { cin n m; for(int i 1; i n; i) cin a[i]; dequeint q; // 递增 - 存下标 // 找最小值 for(int i 1; i n; i) { while(q.size() a[q.back()] a[i]) q.pop_back(); // 递增队尾大于a[i]就出队 q.push_back(i); // 判断窗口合法 if(q.back() - q.front() 1 m) q.pop_front(); // 满足窗口大小就输出 if(i m) cout a[q.front()] endl; } return 0; }四、总结通过上面介绍内容比较多这里总结了单调栈的使用即简单的记忆方法。总结寻找滑动窗口最大值递减的单调队列寻找滑动窗口最小值递增的单调队列关于代码最关键的就是什么是在队尾出队的一段代码。我的建议的方法就是通过判断求的是最大还是最小来判断是递增还是递减从而确认什么是否该写什么时候写 。即如果是求最大值则是递减队列要保证递减则只要遇到 a[i] 大于等于 队尾就出队即while(q.size() a[q.back()] a[i]) q.pop_back();如果是求最小值则是递增队列要保证递增则只要遇到 a[i] 小于等于 队尾就出队即while(q.size() a[q.back()] a[i]) q.pop_back();对于我自己理解的是个人观点大于和小于都试一下。求最大值如果 ar[i] 大于 队尾则说明队尾没用了就要出队因为 ar[i] 更大说明队尾一定不是当前以及后面窗口的最大所以就没用了。求最小值如果 ar[i] 小于 队尾则说明队尾没用了就要出队因为 ar[i] 更小说明队尾一定不是当前以及后面窗口的最小所以就没用了。感谢各位观看希望大家多多支持
【算法】数据结构_单调队列
目录一、什么是单调队列二、单调队列解决的问题三、例题解决1. P1886 【模板】单调队列 / 滑动窗口 - 洛谷2. P2251 质量检测 - 洛谷四、总结一、什么是单调队列单调队列顾名思义就是存储的元素要么单调递增要么单调递减的队列。其实就是我们要维护一个单调递增要么单调递减的队列来解决问题。注意这里的队列不是普通的队列他是一个双端队列链接deque - C Reference。二、单调队列解决的问题通过单调队列我们解决的问题是在滑动窗口中寻找最大值或最小值的问题。除此之外它还可以用来优化动态规划的问题以后说。三、例题解决下面我们就来通过两个例题来理解如何使用单调队列的。1. P1886 【模板】单调队列 / 滑动窗口 - 洛谷题目链接P1886 【模板】单调队列 / 滑动窗口 - 洛谷问题内容题目分析这道题就是让我们在一个数组中从前往后遍历每次遍历都在区间 [ i, i k - 1 ] 区间中找到此时这段长度为k区间中的最大值和最小值直到 i k - 1 到达数组末尾。解决思路这道题就是一个经典的关于双端队列的模板题目这里的队列中存储的是元素的下标这里设置下标从1开始。如果我们将队列中存储的值设置为就是元素的值而不是下标则我们可以以示例数组为 [ 3, 1, 15, 10, 7, 2, 5, 14, 14 ] 窗口大小 k 3 那么我们可以来模拟一下这里设置下标从1开始初始时如图所示其中 ret[ i ] 表示以i位置为结尾的窗口中的最大值的值。假设我们要求滑动窗口中的最大值模拟过程如下所示我们需要从左向右遍历每一个元素遇到第1个元素 3 时此时还没有形成长度为 k 的窗口就将 3 入队得遇到第 2 个元素1 时此时仍没有形成长度为 k 的窗口但是需要和前一个队尾元素比较此时队尾元素大于当前元素则需要就将 1 入队因为1可能是后面窗口中的最大值比如如果从1开始此时窗口中是1 -1 -2, 则此时最大值就是 1得可以发现此时队列就呈现出来递减的趋势了。遇到第 3 个元素15 时此时就形成了一个窗口。比较它和队尾元素的大小此时队尾元素小于15所以可以将队尾元素出队这里可以出队的原因是因为15比1大且靠后所以在包含15往后的窗口中的最大值一定是15而不会是1即队尾元素必定不是之后某个窗口中的最大值同理1 从队尾出队后此时队尾为3也小于15所以也要出队此时队列为空就需要将 15 入队所以此时这里的窗口中最大值就是15即完成上述操作后的队头。得遇到第4个元素 10 时此时将窗口右移窗口中的数就是[ 1, 15, 10 ] 。队尾元素15大于10此时就需要将10入队因为10不是当前这个窗口的最大值但也可能是后面摸个窗口中最大值所以此时窗口中的最大值是 15即队头元素的值最后更新结果 ret[ 4 ] 15。得遇到第 5 个元素 7 时此时将窗口右移窗口中的数就是[ 15, 10, 7 ] 。队尾元素10大于7此时就需要将7入队理由同上所以此时窗口中的最大值是 15即队头元素的值最后更新结果 ret[ 5 ] 15。得遇到第 6 个元素 2 时此时将窗口右移窗口中的数就是[ 10, 7, 2 ] 。队尾元素7大于2此时就需要将2入队理由同上此时窗口中的最大值是应该是 10但是此时队头元素还是15因为此时15已经不在窗口中了所以在更新结果前我们还需要判断一下当前队列中的元素是否都在当前窗口中判断方法就是在队列中存下标判断队头和队尾之前的下标范围即可最后更新结果 ret[ 6 ] 10。得遇到第 7 个元素 5 时此时将窗口右移窗口中的数就是[ 7, 2, 5 ] 。队尾元素2小于5此时需要将队尾元素出队因为当前队尾元素小于5那么在之后包含5的所以窗口中的最大值一定会比5大此时小于5的队尾元素就没有用了。当前队列中的数据为[ 10(队头), 7(队尾) ]再判断队尾元素为7大于5此时就将5入队。入队后此时需要判断一下当前队列中的元素是否都在窗口中此时10已经不在窗口中了所以需要在队头出队此时队列中数据就是[ 7(队头), 5(队尾) ] 所以当前窗口中的最大值就是队头元素 7 即 ret[ 7 ] 7。得遇到第 8 个元素 14 时此时将窗口右移窗口中的数就是[ 2, 5, 14 ] 。此时队尾元素 5 小于 14需要队尾出队。出队后此时队尾为 7 也小于 14也出队此时队列为空将 14 入队此时队头为 14 14 也满足在窗口内所以直接更新结果 ret[ i ] 14。得对到第9个元素 14 时此时将窗口右移窗口中的数就是[ 5, 14, 14 ] 。此时队尾元素等于 14 。为了保证 14 这个值在后续窗口中判断窗口合法所以我们需要将 队尾这个相等的 14 扔掉即出队。此时队列中队头为14这是新加入的14下标是9。同时此时队列中元素都在窗口中所以更新结果 ret[ 9 ] 14。得通过上面这个找最大值的模拟过程我们就可以总结出通过双端队列找最大值的思路设双端队列为q注意其中存的是下标数组为 arr窗口大小为 k。从左向右开始遍历所有大小为k的窗口。如果队列为空则将 arr[ i ] 的下标入队。如果队列非空则需要判断若队尾 arr[ q.back() ]小于等于arr[ i ] 则说明队尾元素不是后面某个窗口的最大值了需要从队尾出队即 q.pop_back()若队尾 arr[ q.back() ]大于arr[ i ] 需要将arr[ i ] 的下标入队因为当前 元素 可能是包含自己的之后窗口中的最大值。然后判断窗口合法即当前队列中的元素是否都是当前窗口中的元素则以当前遍历到的元素为结尾的窗口中最大值就是当前队列的队头元素。重复2,3,4步骤即可。所以找最大值时双端队列就是一个呈现递减的队列。同理对于寻找窗口的最小值的思路为如果队列为空则将 arr[ i ] 的下标入队。如果队列非空则需要判断若队尾 arr[ q.back() ]大于等于arr[ i ] 则说明当前元素更小队尾元素就再不是后面某个窗口的最小值了需要从队尾出队即 q.pop_back()若队尾 arr[ q.back() ]小于arr[ i ] 需要将arr[ i ] 的下标入队因为当前 元素 可能是包含自己的之后窗口中的最小值。然后判断窗口合法即当前队列中的元素是否都是当前窗口中的元素则以当前遍历到的元素为结尾的窗口中最大值就是当前队列的队头元素。所以找最小值时双端队列就是一个呈现递增的队列。在这道题中我们不需要将它们的结构都保存起来只需要找到后直接输出即可。最后我们实现一下这道题的代码#include iostream #include deque using namespace std; const int N 1e6 1; int n, k; int arr[N]; int main() { cin n k; for(int i 1; i n; i) cin arr[i]; dequeint q; // 双端队列 - 存下标 // 找最小值 for(int i 1; i n; i) { while(q.size() arr[q.back()] arr[i]) q.pop_back(); // 当前比队尾小则队尾一定不是当前窗口的最小队尾就没用了 // q为空 // arr[i]比队尾大--当前可能是后面某个窗口的最小值 q.push_back(i); // 判断队列中的元素是否都在窗口中 -- 窗口合法检查 if(q.back() - q.front() 1 k) q.pop_front(); // 队头出队 // 输出合法窗口的结果 if(i k) cout arr[q.front()] ; } cout endl; q.clear(); // 清空队列 // 找最大值 for(int i 1; i n; i) { while(q.size() arr[q.back()] arr[i]) q.pop_back(); // 当前比队尾大则队尾一定不是当前窗口的最大队尾就没用了 q.push_back(i); if(q.back() - q.front() 1 k) q.pop_front(); if(i k) cout arr[q.front()] ; } return 0; }2. P2251 质量检测 - 洛谷题目链接P2251 质量检测 - 洛谷问题内容解决方法这道题就可以转化为在一个分值数组 a 中寻找以 m 长度大小的一段区间中分值的最小值也就是以 i 为结尾的满足窗口大小为 m 的区间中数值的最小值。所以这就是一个单调队列寻找最小值的应用题直接使用单调队列模拟即可。实现代码为#include iostream #include deque using namespace std; const int N 1e5 10; int n, m; int a[N]; int main() { cin n m; for(int i 1; i n; i) cin a[i]; dequeint q; // 递增 - 存下标 // 找最小值 for(int i 1; i n; i) { while(q.size() a[q.back()] a[i]) q.pop_back(); // 递增队尾大于a[i]就出队 q.push_back(i); // 判断窗口合法 if(q.back() - q.front() 1 m) q.pop_front(); // 满足窗口大小就输出 if(i m) cout a[q.front()] endl; } return 0; }四、总结通过上面介绍内容比较多这里总结了单调栈的使用即简单的记忆方法。总结寻找滑动窗口最大值递减的单调队列寻找滑动窗口最小值递增的单调队列关于代码最关键的就是什么是在队尾出队的一段代码。我的建议的方法就是通过判断求的是最大还是最小来判断是递增还是递减从而确认什么是否该写什么时候写 。即如果是求最大值则是递减队列要保证递减则只要遇到 a[i] 大于等于 队尾就出队即while(q.size() a[q.back()] a[i]) q.pop_back();如果是求最小值则是递增队列要保证递增则只要遇到 a[i] 小于等于 队尾就出队即while(q.size() a[q.back()] a[i]) q.pop_back();对于我自己理解的是个人观点大于和小于都试一下。求最大值如果 ar[i] 大于 队尾则说明队尾没用了就要出队因为 ar[i] 更大说明队尾一定不是当前以及后面窗口的最大所以就没用了。求最小值如果 ar[i] 小于 队尾则说明队尾没用了就要出队因为 ar[i] 更小说明队尾一定不是当前以及后面窗口的最小所以就没用了。感谢各位观看希望大家多多支持
