单调队列

定义

单调队列是一个限制只能队尾插入，但是可以两端删除的双端队列。单调队列存储的元素值，是从队首到队尾单调递增或单调递减的。

运用情况

1. 滑动窗口最大值：给定一个整数数组和一个窗口大小，计算窗口内的最大值。
2. 任务调度：按照任务的优先级或其他条件进行调度。
3. 资源分配：根据资源的需求和可用情况进行分配。
4. 数据压缩：通过去除重复或冗余数据来压缩数据。

注意事项

1. 确保队列的单调性：在插入和删除元素时，要保持队列的单调性。
2. 处理边界情况：特别注意队首和队尾的操作，以及空队列的情况。
3. 元素的比较和排序：根据具体问题，确定合适的元素比较和排序方式。
4. 时间复杂度：考虑插入、删除和查询操作的时间复杂度，确保算法的效率。

解题思路

1. 分析问题：确定问题是否适合使用单调队列，以及需要维护的单调性。
2. 定义队列：根据问题的要求，选择合适的数据结构来实现单调队列。
3. 插入和删除元素：按照单调队列的规则，进行元素的插入和删除操作。
4. 获取结果：根据问题的需求，从单调队列中获取所需的结果，如最大值、最小值或特定位置的元素。
5. 优化和改进：根据具体情况，考虑对算法进行优化，如使用更高效的数据结构或改进插入和删除的方式。

Acwing.154滑动窗口

题目描述

154. 滑动窗口 - AcWing题库

运行代码

#include<iostream>
using namespace std;
int a[1000010],q[1000010];
int tt=0,hh=1,i,k,n;

void chu ()
{
    tt=0;hh=1;
}

int main ()
{
    
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++)
    {
       
        while(hh<=tt&&a[i]<a[q[tt]]) tt--;
    q[++tt]=i;
    if(q[hh]<=i-k) hh++;
    if(i>=k) 
    {printf("%d ",a[q[hh]]);}
    }
    printf("\n");
    chu();
    for(int i=1;i<=n;i++)
    {
        
       while(hh<=tt&&a[i]>a[q[tt]]) tt--;
    q[++tt]=i;
    if(q[hh]<=i-k) hh++;
    if(i>=k) {printf("%d ",a[q[hh]]);}
    }
    
}

代码思路

1. 变量定义：
   • a[1000010]：存储输入的数组。
   • q[1000010]：模拟双端队列，存储数组a中元素的索引。
   • tt 和 hh：分别表示队列的尾部和头部索引。
   • n 和 k：分别表示数组的长度和滑动窗口的大小。
2. 读取输入：
   • 使用scanf读取数组的长度n和滑动窗口的大小k。
   • 使用scanf读取数组a的元素。
3. 处理滑动窗口的最小值：
   • 遍历数组a。
   • 使用while循环确保队列q中的元素对应的数组值从队头到队尾是递增的（因为要找最小值）。
   • 如果当前元素a[i]小于队尾元素对应的值a[q[tt]]，则弹出队尾元素，直到队列为空或找到不小于a[i]的元素。
   • 将当前索引i加入队尾。
   • 如果队头索引对应的元素已经滑出窗口（即q[hh] <= i - k），则弹出队头元素。
   • 如果当前窗口大小达到k，则输出队头元素对应的值，即当前窗口的最小值。
4. 输出换行符并重置队列：
   • 调用chu()函数（虽然这里命名为chu可能不太直观，但实际上是重置队列的索引）。
5. 处理滑动窗口的最大值：
   • 与处理最小值类似，但这次要确保队列中的元素从队头到队尾是递减的（因为要找最大值）。
   • 遍历数组a，并使用类似的逻辑来维护队列和输出最大值。

注意：

• 代码中chu()函数实际上只在处理完最小值后被调用一次，用于重置队列索引，以便接下来处理最大值。
• 由于q数组实际上被用作双端队列，因此tt和hh的更新逻辑与双端队列的入队和出队操作类似。
• 代码中并没有显式地检查输入的有效性（例如，n和k的值是否合理，k是否小于等于n等），但在实际应用中应该添加这些检查。
• 变量命名（如chu）可能不够直观，建议使用更具描述性的名称来提高代码的可读性。

改进思路

创建了两个队列 minQ 和 maxQ 分别用于存储最小值和最大值的索引。同时，我也将处理最小值和最大值的逻辑分别封装在 processMin 和 processMax 函数中。在 main 函数中，我首先用 processMin 函数处理最小值，然后重置队列索引并调用 processMax 函数处理最大值。

注意，我还将队列的最大大小定义为常量 MAXN，这是为了避免在代码中硬编码数字。

改进代码

#include<iostream>  
using namespace std;  
const int MAXN = 1000010;  
int a[MAXN], minQ[MAXN], maxQ[MAXN];  
int minTT = 0, minHH = 1, maxTT = 0, maxHH = 1, n, k;  
// 辅助函数，用于处理滑动窗口的最小值  
void processMin() {  
    for(int i = 1; i <= n; i++) {  
        // 维护最小值队列  
        while(minHH <= minTT && a[i] < a[minQ[minTT]]) minTT--;  
        minQ[++minTT] = i;  
        // 移除窗口最左边的元素  
        if(i - minQ[minHH] + 1 > k) minHH++;  
        // 当窗口大小达到k时，输出结果  
        if(i >= k) printf("%d ", a[minQ[minHH]]);  
    }  
    printf("\n");  
}  
// 辅助函数，用于处理滑动窗口的最大值  
void processMax() {  
    for(int i = 1; i <= n; i++) {  
        // 维护最大值队列  
        while(maxHH <= maxTT && a[i] > a[maxQ[maxTT]]) maxTT--;  
        maxQ[++maxTT] = i;  
        // 移除窗口最左边的元素  
        if(i - maxQ[maxHH] + 1 > k) maxHH++;  
        // 当窗口大小达到k时，输出结果  
        if(i >= k) printf("%d ", a[maxQ[maxHH]]);  
    }  
    printf("\n");  
}  
  
int main() {  
    scanf("%d%d", &n, &k);  
    for(int i = 1; i <= n; i++) {  
        scanf("%d", &a[i]);  
    }  
    // 处理滑动窗口的最小值  
    processMin();  
    // 处理滑动窗口的最大值，重置队列索引  
    minTT = 0, minHH = 1, maxTT = 0, maxHH = 1;  
    processMax();  
    return 0;  
}