单调队列

id: monotonic_queue

[[toc]]

入门题目 : luogu P1886 滑动窗口 /【模板】单调队列

解析

核心思想: 截断

  • 每一次都会增加一个值,向窗口内
  • 假如窗口内的值本身是有序的呢?
  • 那些比自己大的队列内的值,一定比自己早出现,被自己截断了

实现

  • 创建一个双端队列，可以从头和尾删除
  • 从队列中头部取值：
    1. 先把那些超过范围数值,删除
    2. 再取值
  • 向队列尾部push新值v
    1. 把那些没有v优秀的值，都删除
    2. 再push v
  • 按这样操作，队列中的值是有序的
一句话算法

去除那些不可能是答案的值,保留那是可以是答案的值

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+5;
int n,k;
int a[maxn];

//队列的模板
template<typename T = int,int siz = maxn>
struct myqueue{
    T a[siz+5];
    //tail 指向最后一个元素后面一个位置
    //head 指向第一个元素
    int head = 0,tail=0; 

    void clear() { head =tail = 0;}

    void push(T b) { a[tail++] = b;}

    void pop(){head++;}
    void pop_back(){tail--;}

    T front() { return a[head];}
    T back() { return a[tail-1];}

    bool empty() { return head == tail;}

    int size() { return tail-head;}

    void debug() {
        cout << "queue : ";
        for(int i =  head ;i < tail;i++) {
            cout << a[i] << " ";
        }
        cout << endl;
    }
};

myqueue<int> que;


int main () {
    //读取数据
    std::cin >> n >> k;
    for(int i = 1;i <= n ;++i ) // i: 1->n
        cin >> a[i];
    // 求最小值
    // 1. 先放k个值
    for(int i = 1;i<k;i++) {
        int v = a[i];
        //那些比v的大的都不可能是答案
        while( !que.empty() && a[que.back()] >= v) {
            que.pop_back();
        }
        que.push(i);
    }
    for(int i = k;i<=n;i++) {
        int v = a[i];
        //那些比v的大的都不可能是答案
        while( !que.empty() && a[que.back()] >= v) {
            que.pop_back();
        }
        // 加入 
        que.push(i);
        //删除越界的值
        while( !que.empty() && que.front() < i-k+1)
            que.pop();
        cout << a[que.front()] <<" ";
    }
    cout << endl;

    que.clear();
    for(int i = 1;i<k;i++) {
        int v = a[i];
        //那些比v的小的都不可能是答案
        while( !que.empty() && a[que.back()] <= v) {
            que.pop_back();
        }
        que.push(i);
    }

    // 求最大值
    for(int i = k;i<=n;i++) {
        int v = a[i];
        //那些比v的小的都不可能是答案
        while( !que.empty() && a[que.back()] <= v) {
            que.pop_back();
        }
        // 加入
        que.push(i);
        //删除越界的值
        while( !que.empty() && que.front() < i-k+1)
            que.pop();
        cout << a[que.front()] <<" ";
    }
    cout << endl;

    return 0;
}

题目2: 最大子序和

核心思想: 截断

https://www.acwing.com/problem/content/137/

根据[[缩小放大法]]

情况1: 所有的数都是正数,变成区间和问题,可以使用前缀和来解

情况2: 不限制M或M很大超过了N,那么就成最大连续区间和问题,可以使用DP. 对应题目: luogu-P1115

思考🤔一下能不能用DP解这个题目呢?简单的想一个,不能,应该需要记录长度信息,f(i,j)f(i,j)表示以ii结尾的子序列前j个元素的和,这样时间变成了n×mn \times m,超时了.

按通常的思路来,静态区间和转成对就的前缀和数组上的两个数想减,设S[i]S[i]表示前ii个元素的和,那么区间[l,r][l,r]的和,就是s[r]−s[l−1]s[r]-s[l-1].

那么这个问题就转化为:

f(i)=max⁡j=i−Mi−1{S[i]−S[j−1]} \begin{gather} f(i) = \max_{j=i-M}^{i-1}\{ S[i] - S[j-1] \} \end{gather}

以因为S[i]S[i]不需要动,是一个定值

f(i)=S[i]−min⁡j=i−Mi−1{S[j−1]} \begin{gather} f(i) = S[i] - \min_{j=i-M}^{i-1}\{S[j-1] \} \end{gather}

问题转化成,固定区间最小值: 当ii固定时,求j∈[i−m,i−1]j \in [i-m,i-1]中,使得S[j−1]S[j-1]最小的jj.

那这个问题就成成了[[../滑动窗口]]问题.

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+5;
int n,k;
int s[maxn]; //前缀和
int ans = -2147483648; // 最小的负数

//队列的模板
template<typename T = int,int siz = maxn>
struct myqueue{
    T a[siz+5];
    //tail 指向最后一个元素后面一个位置
    //head 指向第一个元素
    int head = 0,tail=0; 

    void clear() { head =tail = 0;}

    void push(T b) { a[tail++] = b;}

    void pop(){head++;}
    void pop_back(){tail--;}

    T front() { return a[head];}
    T back() { return a[tail-1];}

    bool empty() { return head == tail;}

    int size() { return tail-head;}

    void debug() {
        cout << "queue : ";
        for(int i =  head ;i < tail;i++) {
            cout << a[i] << " ";
        }
        cout << endl;
    }
};

myqueue<int> que;

int main () {
    //读取数据
    std::cin >> n >> k;
    //前缀和
    for(int i = 1;i <= n ;++i ) // i: 1->n
    {
        cin >> s[i];
        s[i] += s[i-1];
    }
    que.push(0); //加入一个前缀和s[0]
    // 求最小值
    for(int i = 1;i<=n;i++) {
        //删除越界的值
        while( !que.empty() && que.front() < i-k)
            que.pop();

        ans = max(ans,s[i]- s[que.front()]);

        int v = s[i];
        //为了保证不会减去自己s[i],所以在计算完之后才添加s[i]
        //那些比v的大的都不可能比v更好
        while( !que.empty() && s[que.back()] >= v) {
            que.pop_back();
        }
        // 加入 
        que.push(i);
    }
    cout << ans << endl;
    return 0;
}

总结

为什么可以有单调队列这种形式呢?

核心思想

  1. 排除不可能的选项(不超时)
  2. 去除超时选项
  3. 保留可能选项

自然而然的就造成了单调队列这种结构.

  • 单调栈是单调队列的特殊形式
一句话算法

如果状态AA与状态BB与的前置决策空间PA,PBP_A,P_B

  • PA,PBP_A,P_B有重叠
  • PA,PBP_A,P_B类似有滑动窗口的关系(进一出一)

那么从AA到BB可以使用单调队列优化.

一句话算法

动态的维护滑动区间的投影队列