单调队列学习笔记

单调队列

​ 单调队列和单调栈基本类似，但是，单调队列一般用来维护连续的长度为 \(k\)​ 的区间的最值（滑动窗口），所以一般需要从前面弹出数——这是和单调栈很大的一个区别。

​ 形象地举个例子，给出每个年级的综合实力，要求求当前学校大一到大四的实力最大值，我们用单调队列来维护：如果新加入的一个年级的实力很小，但是可能前面的几个年级毕业了就让它成为最大值了（山中无老虎，猴子称霸王），但是如果新加入的数比前面的数还大，只要区间存在新加入的数，前面的数无论如何都不可能成为最大值了，而且求出区间的最值是在线的，即一个数加入就能求出以这个数为结尾的区间的最值，所以前面的数已经没有贡献了，直接弹出。同时，每次新加入前需要弹出前面毕业的年级。

​ 因此，维护滑动窗口最大值，需要一个从队头到队尾单调递减的队列。一个和单调栈类似的记法是：需要最大值，弹出时用大于号比较新加入的值；需要最小值，弹出时用小于号比较。

​ 由于需要双向弹出，实现上可以选择 deque，与单调栈的唯一区别是控制队列的长度（pop_front 操作)。

下面是模版题：滑动窗口

本人的代码实现：规定一个指针 pos ，使用双指针的思想，对于每个 \(i\) 将 pos 能到达的区域加入单调队列，先加入后更新，如果有单调队列为空的风险的话特判一下。

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    deque<int> q;
    int pos = 1;

    for (int i = k; i <= n; i++) {
        while (pos <= i) {
            while (!q.empty() && a[pos] < a[q.back()]) {
                q.pop_back();
            }
            q.push_back(pos);
            pos++;
        }
        while (!q.empty() && i - q.front() >= k) {
            q.pop_front();
        }
        cout << a[q.front()] << " \n"[i == n];
    }

    q.clear();
    pos = 1;
    for (int i = k; i <= n; i++) {
        while (pos <= i) {
            while (!q.empty() && a[pos] > a[q.back()]) {
                q.pop_back();
            }
            q.push_back(pos);
            pos++;
        }
        while (!q.empty() && i - q.front() >= k) {
            q.pop_front();
        }
        cout << a[q.front()] << " \n"[i == n];
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

例题

P2216 [HAOI2007] 理想的正方形

有一个 \(a \times b\) 的整数组成的矩阵，现请你从中找出一个 \(n \times n\) 的正方形区域，使得该区域所有数中的最大值和最小值的差最小。

题解

我们用单调队列处理每一行，就得到了每一行中 \(1\times n\) 大小的最值情况，然后再用单调队列处理每一列，就能得到每一列中 \(n\times n\) 的最值情况，然后 \(O(n^2)\) 遍历一遍求答案即可。

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

void solve() {
    int a, b, n;
    cin >> a >> b >> n;
    vector<vector<int>> mat(a + 1, vector<int>(b + 1)),
        mn(a + 1, vector<int>(b - n + 1)), mx(a + 1, vector<int>(b - n + 1));
    for (int i = 1; i <= a; i++) {
        for (int j = 1; j <= b; j++) {
            cin >> mat[i][j];
        }
    }

    deque<int> qmn, qmx;
    for (int i = 1; i <= a; i++) {
        qmn.clear();
        qmx.clear();
        for (int j = 1; j <= b; j++) {
            if (!qmn.empty() && j - qmn.front() >= n) {
                qmn.pop_front();
            }
            while (!qmn.empty() && mat[i][j] < mat[i][qmn.back()]) {
                qmn.pop_back();
            }
            qmn.push_back(j);
            if (j >= n) {
                mn[i][j - n + 1] = mat[i][qmn.front()];
            }

            if (!qmx.empty() && j - qmx.front() >= n) {
                qmx.pop_front();
            }
            while (!qmx.empty() && mat[i][j] > mat[i][qmx.back()]) {
                qmx.pop_back();
            }
            qmx.push_back(j);
            if (j >= n) {
                mx[i][j - n + 1] = mat[i][qmx.front()];
            }
        }
    }
    for (int j = 1; j <= b - n + 1; j++) {
        qmn.clear();
        qmx.clear();
        for (int i = 1; i <= a; i++) {
            if (!qmn.empty() && i - qmn.front() >= n) {
                qmn.pop_front();
            }
            while (!qmn.empty() && mn[i][j] < mn[qmn.back()][j]) {
                qmn.pop_back();
            }
            qmn.push_back(i);
            if (i >= n) {
                mn[i - n + 1][j] = mn[qmn.front()][j];
            }

            if (!qmx.empty() && i - qmx.front() >= n) {
                qmx.pop_front();
            }
            while (!qmx.empty() && mx[i][j] > mx[qmx.back()][j]) {
                qmx.pop_back();
            }
            qmx.push_back(i);
            if (i >= n) {
                mx[i - n + 1][j] = mx[qmx.front()][j];
            }
        }
    }
    int ans = 2e9;
    for (int i = 1; i <= a - n + 1; i++) {
        for (int j = 1; j <= b - n + 1; j++) {
            ans = min(ans, mx[i][j] - mn[i][j]);
        }
    }
    cout << ans << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

单调队列优化 dp

单调队列代码简短而好写，能够解决的问题范围清晰，是一种很实用的数据结构。单调队列不常作为一个裸的知识点来单独考，而是常常与动态规划等问题结合在一起，用作优化时间复杂度。

一个很明显的单调队列优化特征是：在定长区间取最值进行状态转移。

例题

洛谷 P1725

给定数组 \(a_i\)，到达位置 \(i\) 时会获得 \(a_i\) 的值，往下一个位置走只能到达 \([i+l, i+r]\) 求走过 \(n\) 之后能获得的最大值。

题解

设 \(dp_i\) 为到达 \(i\) 能获得的最大值，注意一旦跳过 \(n\) 就不能获得权值了，所以答案就是 \(\max_{i = n -r+1}^n dp_i\)。

考虑状态转移，既然只能走到 \([i+l,i+r]\)，那么一定有 \(f_i = \max_{j=i-r}^{i-l}(dp_j + a_i)\) ，那么我们有一个 \(O(nr)\) 的做法，最坏就是 \(O(n^2)\) （但是居然能过？）注意遍历的起点是 \(l\)，因为 \([1,l-1]\) 都不可能到达。

void solve() {
    int n, l, r;
    cin >> n >> l >> r;
    vector<int> a(n + n);
    for (int i = 0; i <= n; i++) {
        cin >> a[i];
    }
    int ans = -(1 << 30);
    vector<int> dp(n + n, -(1 << 29));
    dp[0] = 0;
    for (int i = l; i <= n + r - 1; i++) {
        for (int j = max(0, i - r); j <= i - l; j++) {
            dp[i] = max(dp[i], dp[j] + a[i]);
        }
        if (i + r > n) {
            ans = max(ans, dp[i]);
        }
    }
}

当然正常情况下肯定是会 TLE 的，需要优化，注意到我们只需要 \([i-r, i-l]\) 的最大值，这是一个定长区间，同时我们需要最值，自然想到了单调队列优化。因此我们使用单调队列维护 \([i-r,i-l]\) 的最大值，更新状态即为 \(dp_i = dp_j + a_i\) （$j $ 为单调队列最大值）

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

void solve() {
    int n, l, r;
    cin >> n >> l >> r;
    vector<int> a(n + n);
    for (int i = 0; i <= n; i++) {
        cin >> a[i];
    }
    int ans = -(1 << 30);
    vector<int> dp(n + n, -(1 << 29));
    dp[0] = 0;
    deque<int> q;
    for (int i = l; i <= n; i++) {
        if (!q.empty() && q.front() < i - r) {
            q.pop_front();
        }
        while (!q.empty() && dp[i - l] > dp[q.back()]) {
            q.pop_back();
        }
        q.push_back(i - l);
        dp[i] = dp[q.front()] + a[i];
        if (i + r > n) {
            ans = max(ans, dp[i]);
        }
    }
    cout << ans << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

洛谷 P3800

\(n\) 行 \(m\) 列的网格，给定 \(k\) 个点，权值为 \(v_i\)，可以选择在第一行的任意一个位置出发，每秒她必须下移一格，同时可以左右移动至多 \(t\) 格，获得目标点上的权值。求到达最后一行能获得的最大权值。

题解

设 \(dp_{i,j}\) 为到达 \((i,j)\) 所能获得的最大权值，那么显然有 \(dp_{i,j} = \max_{y=j-t}^{j+t}dp_{i-1,y} + a_{i,j}\)， max 部分使用单调队列优化即可。

本题在单调队列实现上需要注意的是，由于 \(dp_y\) 的答案不是移动到 \(y\) 就能获得的，而是需要移动到 \(dp_{y+t}\)，因此先把前面一部分数放入当单调队列中，使用 \(l,r\) 维护区间，每次更新一个数。具体可见代码。

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

void solve() {
    int n, m, k, t;
    cin >> n >> m >> k >> t;
    vector<vector<int>> a(n + 1, vector<int>(m + 1));
    for (int i = 1; i <= k; i++) {
        int x, y, v;
        cin >> x >> y >> v;
        a[x][y] = v;
    }
    vector<vector<int>> dp(n + 1, vector<int>(m + 1));
    int len = 2 * t + 1;
    for (int i = 1; i <= n; i++) {
        deque<int> q;
        for (int j = 1; j <= min(m, t); j++) {
            while (!q.empty() && dp[i - 1][j] > dp[i - 1][q.back()]) {
                q.pop_back();
            }
            q.push_back(j);
        }
        int l = t + 1, r;
        for (int j = 1; j <= m; j++) {
            int l = max(1, j - t);
            int r = min(m, j + t);
            while (!q.empty() && q.front() < l) {
                q.pop_front();
            }
            while (!q.empty() && dp[i - 1][r] > dp[i - 1][q.back()]) {
                q.pop_back();
            }
            q.push_back(r);
            dp[i][j] = dp[i - 1][q.front()] + a[i][j];
        }
    }
    int ans = 0;
    for (int j = 1; j <= m; j++) {
        ans = max(ans, dp[n][j]);
    }
    cout << ans << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

洛谷 P2627 P2034

给定 \(n\) 个值 \(a_i\)，选择一些数使得和最大，选择的数字中连续位置的数量不能超过 \(k\)，求最大和。

题解

选择 \(k\) 个数难以转移，我们正难则反，由于连续的数字不能超过 \(k\) ，所以对于不选的位置，它们之间的距离不能超过 \(k+1\)。

设 \(dp_i\) 代表在不选 \(a_i\) 的情况下，没有选择的数的最小和，那么有 \(dp_i = \min_{j=i-k-1}^{i-1}dp_j + a_i\)，可以单调队列优化。要注意 dp 更新的位置，由于只需要到 \(dp_{i-1}\)，因此先更新 \(dp_i\) 再加入单调队列。那么结果就是所有数总和减去 \(\min_{i=n-m-1}^ndp_i\)

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

void solve() {
    int n, k;
    cin >> n >> k;
    int len = k + 1;
    i64 sum = 0;
    vector<int> a(n + 1);
    vector<i64> dp(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum += a[i];
    }
    deque<int> q;
    for (int i = 1; i <= n; i++) {
        if (i > len) {
            dp[i] = dp[q.front()] + a[i];
        } else {
            dp[i] = a[i];
        }
        if (!q.empty() && i - q.front() >= len) {
            q.pop_front();
        }
        while (!q.empty() && dp[i] < dp[q.back()]) {
            q.pop_back();
        }
        q.push_back(i);
    }
    cout << sum - *min_element(dp.end() - len, dp.end()) << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

洛谷 P1419

给定一个长度为 n 的序列 a，定义 \(a_i\) 为第 i 个元素的价值。现在需要找出序列中最有价值的“段落”。段落的定义是长度在 [S,T] 之间的连续序列。最有价值段落是指平均值最大的段落。

段落的平均值 等于 段落总价值 除以 段落长度。

题解

求平均值最大考虑二分答案，原因有两点：一是答案具有单调性，本题中如果平均值 \(x\) 满足条件，那么比 \(x\) 小的数一定满足条件；同时，我们知道平均值的上下界一定是数组元素的最值，那么可以进行二分。

考虑判断平均值为 \(x\) 时是否成立，那么有： \[ \frac{\sum_{i=l}^ra_i}{r-l+1} \ge x \\\\ 等价于 \sum_{i=l}^ra_i \ge x(r - l + 1)\\\\ 等价于 \sum_{i=1}^r(a_i-x) \ge 0 \] 那么我们求出前缀和后，只需要找到一组长度为 \([s,t]\) 的 \([l,r]\) ，满足 \(pre_r - pre_{l-1} \ge 0\)，由于只要找到即可，我们枚举 \(r\) ，只需要 \(pre_{l-1}\) 的最小值，可以考虑单调队列维护。

一个单调队列的实现细节是，从第一个能满足条件的位置开始枚举，对于区间内的数采用下标比较，具体见代码。

由于浮点数比较麻烦，这里采用了先乘 10000，最后除去的方法。

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

void solve() {
    int n;
    cin >> n;
    int s, t;
    cin >> s >> t;
    vector<i64> a(n + 1);
    i64 lo = 2e9, hi = -1;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] *= 1e4;
        lo = min(lo, a[i]);
        hi = max(hi, a[i]);
    }
    i64 ans = 0;
    while (lo <= hi) {
        i64 m = lo + (hi - lo) / 2;
        auto check = [&](int x) {
            vector<i64> pre(n + 1);
            for (int i = 1; i <= n; i++) {
                pre[i] = pre[i - 1] + a[i] - x;
            }
            deque<int> q;
            for (int i = s; i <= n; i++) {
                if (!q.empty() && q.front() < i - t) {
                    q.pop_front();
                }
                while (!q.empty() && pre[i - s] < pre[q.back()]) {
                    q.pop_back();
                }
                q.push_back(i - s);
                if (pre[i] - pre[q.front()] >= 0) {
                    return true;	
                }
            }
            return false;
        };
        if (check(m)) {
            ans = max(ans, m);
            lo = m + 1;
        } else {
            hi = m - 1;
        }
    }
    double res = ans / (double)10000;
    cout << fixed << setprecision(3) << res << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

P3957 [NOIP 2017 普及组] 跳房子

给定 \(n\) 个格子到上一个格子的距离 \(a\) 和权值 \(b\)，一个人从起点出发，每次必须跳 \(d\) 格，需要获得 \(k\) 权值，也可以花 \(g\) 钱使得跳的距离变为 \([d-g,d+g]\)（但无论如何都不能往回跳），判断获得 \(k\) 权值所需要的最少钱或判断不可能。

题解

考虑二分答案，那么设 \(dp_i\) 表示到达第 \(i\) 个格子能获得的最大权值，那么对于一个距离 \(a[i]\)，状态转移方程为 \(dp_i = \max dp_j + a_i\)，但是要求 \(a_i-d-g \le a_j\le a_i-d+g\)，自然可以通过单调队列维护最值。

这里的单调队列实现尤其需要注意：每次 \(i\) 右移的时候，在其中加入新的满足 \(a_j \le a_i - d + g\) 的 \(j\) （可能不止一个），然后弹出满足 \(a_j < a_i - d - g\) 的 \(j\)，不能改变操作的顺序，因为可能新加入的 \(j\) 也不合法（ \(a_j\le a_i-d+g\) 成立，但是 \(a_j \ge a_i - d - g\) 不成立）。这样加入后无法立即弹出，非法的答案就加入到队列中了。

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

void solve() {
    int n, d, k;
    cin >> n >> d >> k;
    vector<int> a(n + 1), b(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
    }
    int lo = 0, hi = 1e9;
    i64 ans = 1e18;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        auto check = [&](int x) {
            vector<i64> dp(n + 1, -1e18);
            dp[0] = 0;
            deque<int> q;
            int c = max(1, d - x);
            int pos = 0;
            i64 res = 0;
            for (int i = 1; i <= n; i++) {
                while (a[i] - a[pos] >= max(c, 1)) {
                    while (!q.empty() && dp[pos] > dp[q.back()]) {
                        q.pop_back();
                    }
                    q.push_back(pos);
                    pos++;
                }
                while (!q.empty() && a[i] > d + x + a[q.front()]) {
                    q.pop_front();
                }
                if (!q.empty()) {
                    dp[i] = b[i] + dp[q.front()];
                }
                res = max(res, dp[i]);
            }
            return res >= k;
        };
        if (check(mid)) {
            ans = min(ans, 1ll * mid);
            hi = mid - 1;
        } else {
            lo = mid + 1;
        }
    }
    if (ans == 1e18) {
        ans = -1;
    }
    cout << ans << "\n";
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

P2254 [NOI2005] 瑰丽华尔兹

一个 \(n\times m\) 的矩阵存在障碍，给定 \(K\) 个时间区间，每个时间区间包括 \([l,r]\) 和方向 \(d\)，给定起始点，在每个时间区间可以向给定方向走或不走，求最后走过的最大距离。

题解

设 \(dp_{i,j,k}\) 为在 \(t\) 时间的状态，是 \(O(NMT)\) 的复杂度，很不现实，考虑根据时间段进行 dp，设 \(dp_{i,j,k}\) 为在第 \(i\) 段时间，停在坐标 \((j,k)\) 能走过的最大距离，这样的话直接计算需要先枚举每个时间段，然后枚举每个点，由于方向已知，对于这个点可枚举距离进行转移，时间复杂度最大可为 \(O(KNM\times\max(N,M))\)，如果方向是向右的，状态转移方程为：\(dp_{i,j,k} = \max_{j-len\le pos\le i}dp_{i-1,pos,j} + abs(pos - i)\)

还是不行，考虑优化。注意到对一个方向进行转移时，可以更新该方向的所有答案，由于我们只需要最大值，可以使用单调队列优化，均摊复杂度为 \(O(KNM)\)​​，同时可以进行滚动数组优化降低空间复杂度。

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

void solve() {
    int n, m, x, y, k;
    cin >> n >> m >> x >> y >> k;
    vector<string> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] = " " + a[i];
    }
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, -2e9)),
        mdp(n + 1, vector<int>(m + 1, -2e9));
    mdp[x][y] = 0;
    for (int t = 1; t <= k; t++) {
        int s, tt, d;
        cin >> s >> tt >> d;
        int len = tt - s + 2;// 在下面的转移中包含了自身，因此这里距离多了 1
        if (d == 1) {  // 北
            for (int j = 1; j <= m; j++) {
                deque<int> q;
                int pos = n;
                for (int i = n; i >= 1; i--) {
                    if (a[i][j] == 'x') {
                        q.clear();
                        pos--;
                        continue;
                    }
                    while (pos >= i) {
                        while (!q.empty() &&
                               mdp[pos][j] + pos - i >
                                   mdp[q.back()][j] + q.back() - i) {
                            q.pop_back();
                        }
                        q.push_back(pos);
                        pos--;
                    }
                    while (!q.empty() && q.front() - i >= len) {
                        q.pop_front();
                    }
                    dp[i][j] = mdp[q.front()][j] + q.front() - i;
                }
            }
        } else if (d == 2) {  // 南
            for (int j = 1; j <= m; j++) {
                deque<int> q;
                int pos = 1;
                for (int i = 1; i <= n; i++) {
                    if (a[i][j] == 'x') {
                        q.clear();
                        pos++;
                        continue;
                    }

                    while (pos <= i) {
                        while (!q.empty() &&
                               mdp[pos][j] + i - pos >
                                   mdp[q.back()][j] + i - q.back()) {
                            q.pop_back();
                        }
                        q.push_back(pos);
                        pos++;
                    }
                    while (!q.empty() && i - q.front() >= len) {
                        q.pop_front();
                    }
                    dp[i][j] = mdp[q.front()][j] + i - q.front();
                }
            }
        } else if (d == 3) {  // 西
            for (int i = 1; i <= n; i++) {
                deque<int> q;
                int pos = m;
                for (int j = m; j >= 1; j--) {
                    if (a[i][j] == 'x') {
                        q.clear();
                        pos--;
                        continue;
                    }
                    while (pos >= j) {
                        while (!q.empty() &&
                               mdp[i][pos] + pos - j >
                                   mdp[i][q.back()] + q.back() - j) {
                            q.pop_back();
                        }
                        q.push_back(pos);
                        pos--;
                    }
                    while (!q.empty() && q.front() - j >= len) {
                        q.pop_front();
                    }
                    dp[i][j] = mdp[i][q.front()] + q.front() - j;
                }
            }
        } else {  // 东
            for (int i = 1; i <= n; i++) {
                deque<int> q;
                int pos = 1;
                for (int j = 1; j <= m; j++) {
                    if (a[i][j] == 'x') {
                        q.clear();
                        pos++;
                        continue;
                    }
                    while (pos <= j) {
                        while (!q.empty() &&
                               mdp[i][pos] + j - pos >
                                   mdp[i][q.back()] + j - q.back()) {
                            q.pop_back();
                        }
                        q.push_back(pos);
                        pos++;
                    }
                    while (!q.empty() && j - q.front() >= len) {
                        q.pop_front();
                    }
                    dp[i][j] = mdp[i][q.front()] + j - q.front();
                }
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                mdp[i][j] = dp[i][j];
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            ans = max(ans, dp[i][j]);
        }
    }
    cout << ans << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}