【数据结构】【队列】单调队列

单调队列和单调栈有些类似，它们的用途十分有限，但由于算法巧妙优美，所以十分受面试官的青睐。

单调队列主要用在求滑动区间内最值。

例题：

#include <iostream>
#include <vector>

using namespace std;

const int N = 1e6 + 10;

int main()
{
    int n, k;
    vector<int> q; // 用一个vector模拟一个队列，队列中存储的是数的下标
    
    scanf("%d %d", &n, &k);

    int arr[N];
    
    for(int i = 0; i < n; i++)
    {
        scanf("%d", &arr[i]);
    }
    
    
    // 求滑动窗口中的最小值
    for(int i = 0; i < n; i ++ )
    {
        // 如果队列最小值已经不再滑动窗口内，将其删除
        if(!q.empty() && q.front() < i - k + 1) 
            q.erase(q.begin());
        // 如果新进来的值比队列中的最小值还要小，那么将队列中大于当前值的数删除
        while(!q.empty() && arr[q.back()] >= arr[i]) 
            q.pop_back();
        q.push_back(i);
        if(i >= k - 1) printf("%d ", arr[q.front()]);
    }
    // 这个过程下来队列中的数始终保持了有序
    
    cout<<endl;
    
    q.clear();
    
    
    // 求最大值是类似的过程
    for(int i = 0; i < n; i ++ )
    {
        if(!q.empty() && q.front() < i - k + 1) 
            q.erase(q.begin());
        while(!q.empty() && arr[q.back()] <= arr[i])
            q.pop_back();
        q.push_back(i);
        if(i >= k - 1) printf("%d ", arr[q.front()]);
    }
    
    return 0;
    
}