单调栈与单调队列

单调栈

单调栈

1、在栈的基础上，如果保持栈内元素是有序的，则称为单调栈，分为单调递增栈和单调递减栈
2、通常单调栈主要用于求位置最近的更大值或更小值，我们将在具体样例中分析

伪代码模板

int arr[n];
stack<int> stk; // 可存值，可存下标，此处以存值为例

for(int i = 0; i < n; i++)
{
    while(!stk.empty() && arr[i]优于stk.top())
        stk.pop(); // 弹出栈顶

    // 此时栈顶为对目前元素的最优答案
    if(stk.empty())
        栈空的操作
    else
        栈非空的操作

    stk.push(arr[i]); // 当前元素入栈
}

例-单调栈

例-单调栈

1、单调栈：给定长度为 n 的整数数组，求出每个元素左边第一个比它小的元素，如果不存在则输出 -1
2、由题意，我们需要找到位置最近且小于该点的元素，可以使用单调递增栈来维护数据。遍历地向栈内压入元素，如果待压入元素小于等于栈顶元素，就将栈顶元素弹出，直至待压入元素大于栈顶元素再压入该元素。这是因为待压入元素小于等于栈顶元素的情况下，数组右侧元素向左查找时，如果栈顶元素满足条件，那么待压入元素也一定满足条件，且待压入元素的位置更近，这意味着无论如何都不会再使用到栈顶元素，便将其弹出
3、例如数组 $\{1, 3, 4, 2, 5, 7\}$，过程为：遍历 $1$，栈内为空，输出 $-1$，将 $1$ 入栈；遍历 $3$，栈顶为 $1$，输出 $1$，将 $3$ 入栈；遍历 $4$，栈顶为 $3$，输出 $3$，将 $4$ 入栈。但当遍历 $2$ 时，与栈顶比较，$2 \leq 4, 2\leq 3$，弹出 $4$，弹出 $3$，栈顶为 $1$，输出 $1$，将 $2$ 入栈。重要的是，遍历右侧元素($5$ 和 $7$)时，因为有 $2$ 的存在，它更小(更容易满足答案条件)也更近(更近的才是答案)，所以一定不会用到更左边的 $3$ 和 $4$，因此将其从栈内弹出即可

代码实现

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

const int N = 2e5 + 10;
int a[N];

void solve()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];

    stack<int> stk; // 栈内存放元素值
    for (int i = 0; i < n; i++)
    {
        // 如果待压入元素 <= 栈顶元素，且栈非空
        while (!stk.empty() && a[i] <= stk.top())
            stk.pop(); // 弹出栈顶元素

        // 如果栈空，则输出 -1，否则输出栈顶元素
        if (stk.empty())
            cout << -1 << ' ';
        else
            cout << stk.top() << ' ';

        stk.push(a[i]); // 将当前元素压入栈
    }
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T = 1;
    // cin >> T;
    while (T--)
        solve();
    return 0;
}

例-求和

例-求和

1、求和：给定一个大小为 n 的整数序列，求出其所有子区间的最小值之和
2、如果先划分区间再求区间最小值，简单推断可知时间复杂度较高会超时。我们可以换种思路，假定当前元素就是区间最小值，再找有多少个符合条件的区间
3、遍历所有元素 $a[i]$，分别假定每个 $a[i]$ 为区间最小值。每次从 $a[i]$ 先向左遍历，统计向左(包含它自己)连续有多少个比它大的元素(以确保该元素是区间最小值)，记为 $l[i]$ ；再向右遍历，同样统计向右(包含它自己)连续满足条件的元素个数，记为 $r[i]$ ；最后将 $l[i]$ 和 $r[i]$ 相乘(统计这些范围内有多少个区间)，得到以 $a[i]$ 为区间最小值的区间个数 $l[i] * r[i]$。则 $a[i]$ 对答案的贡献为 $a[i] * (l[i] * r[i])$
4、有一种特殊情况是，出现两个相同的值，如 $\{1, 3, 2, 5, 2, 7, 2\}$，此时应该自行定义好规则防止重复统计。例如我们可以规定，统计重复的数时左开右闭(即向左统计时遇到相等值不停止，向右统计时遇到相等值停止)，这样便可以避免重复统计。例如统计 $2$ 时，$\{3, 2\}$、$\{3, 2, 5\}$ 等归第一个 $2$ 统计；$\{2, 5, 2\}$、$\{3, 2, 5, 2\}$、$\{3, 2, 5, 2, 7\}$等归第二个 $2$ 统计；$\{2, 7, 2\}$、$\{3, 2, 5, 2, 7, 2\}$等归第三个 $2$ 统计
5、现在的问题是，如何向左右统计出 $l[i]$ 和 $r[i]$ ？实质还是统计 $a[i]$ 左边/右边位置最近的比它小的元素，因此便可以用单调栈。实际代码为了方便，令 $l[i]$、$r[i]$ 记录截止元素的下标而非直接记录满足的连续元素个数，具体如下代码实现

代码实现

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

#define int long long
const int N = 2e5 + 10;
int a[N], l[N], r[N]; // l[], r[] 并非直接存储有效个数，而是存储截止元素的下标

void solve()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    stack<int> stk; // 存储下标

    // 比对样例 {~, 1, 3, 2, 5, 2, 7, 2}

    // 先求 l[]，左开，向左统计时如果相等可以继续
    // 从左向右的单调递增栈
    for (int i = 1; i <= n; i++)
    {
        // 栈不为空，且当前元素 <= 栈顶
        while (!stk.empty() && a[i] <= a[stk.top()])
            stk.pop();

        // 此时栈顶即为 l[i]，但可能栈为空，栈为空说明左边没有比它小的
        if (stk.empty())
            l[i] = 0; // 向左可以延伸到最尽头，将下标 0 看作尽头无穷小
        else
            l[i] = stk.top(); // stk.top() 为左边最近的比 a[i] 小的元素的位置

        stk.push(i);
    }

    stk = stack<int>(); // 清空栈

    // 再求 r[]，右闭，向右统计时如果相等不能继续
    // 翻转着统计，从右向左的单调递增栈
    for (int i = n; i >= 1; i--)
    {
        // 栈不为空，且当前元素 < 栈顶
        while (!stk.empty() && a[i] < a[stk.top()])
            stk.pop();

        // 此时栈顶即为 r[i]，但可能栈为空，栈为空说明右边没有比它小的
        if (stk.empty())
            r[i] = n + 1; // 向右可以延伸到最尽头，将下标 n+1 看作尽头无穷小
        else
            r[i] = stk.top(); // stk.top() 为右边最近的比 a[i] 小的元素的位置

        stk.push(i);
    }

    int ans = 0;
    // 求解，a[i] 为最小值的区间个数为 (i - l[i]) * (r[i] - i)
    for (int i = 1; i <= n; i++)
        ans += a[i] * (i - l[i]) * (r[i] - i);
    cout << ans;
}

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

单调队列

单调队列

1、单调队列虽然基于队列，但单调队列中的元素值不一定是单调的，而是根据某种规则 $f(x)$ 的值单调的(可能 $f(x) = a[x]$ ，也可能 $f(x) = a[x] * b[x]$ 等)
2、通常单调队列使用双端队列deque来维护，因为队列两头都可以出入。维护过程中始终保持队头为当前最优解，向队尾依次为单调次优解
3、元素入队始终从队尾依次比较，如果该元素更优则当前队尾出队，找到合适位置该元素入队。此外只需要维护队头是否合法，不合法时队头出队即可
4、通常单调队列用于优化各种 DP，解决滑动窗口问题等

伪代码模板

int arr[n];
deque<int> dq;  // 通常存下标更方便管理

for(int i = 0; i < n; i++)
{
    while(!dq.empty() && dq.front()不合法)
        dq.pop_front(); // 弹出队头

    while(!dq.empty() && arr[i]优于dq.back())
        dq.pop_back();  // 弹出队尾

    dq.push_back(i);  // 当前元素下标入队尾
    // 此时队头为最优
    需要的操作
}

例-滑动窗口

例-滑动窗口

1、滑动窗口：给定长度为 $n$ 的整数数组，有一个长度为 $k$ 的窗口从数组最左依次滑动到最右，回答窗口在每个位置时窗口内元素的最大值和最小值
2、在该题中，规则 $f(x) = a[x]$ ，即只需按照元素值大小单调，因此该例的单调队列内元素是升序或降序的
3、思路类似于单调栈，保持队头是当前最优解，从队尾依次检查并弹出不够优越的元素，维护队头向队尾依次为单调次优解

代码实现

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

const int N = 2e5 + 10;
int a[N];

void solve()
{
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; i++)
        cin >> a[i];

    deque<int> dq; // 存放下标

    // 先求最大值
    for (int i = 0; i < n; i++)
    {
        // 窗口为以 i 为右端点，大小为 k 的区间，即窗口为 [i + 1 - k, i]
        // 如果队列非空，并且队头下标非法，即对头元素在窗口外
        while (!dq.empty() && dq.front() < i + 1 - k)
            dq.pop_front(); // 弹出队头

        // 如果队列非空，且当前元素比队尾更大更优越
        while (!dq.empty() && a[i] >= a[dq.back()])
            dq.pop_back(); // 弹出队尾

        dq.push_back(i); // 当前元素下标入队尾
        // 此时队头为最大值

        // 前几次时还没有形成大小为 k 的窗口，形成后队头即为最大值
        if (i >= k - 1)
            cout << a[dq.front()] << ' ';
    }

    cout << '\n';
    dq = deque<int>(); // 清空 dq

    // 再求最小值
    for (int i = 0; i < n; i++)
    {
        // 窗口为以 i 为右端点，大小为 k 的区间，即窗口为 [i + 1 - k, i]
        // 如果队列非空，并且队头下标非法，即对头元素在窗口外
        while (!dq.empty() && dq.front() < i + 1 - k)
            dq.pop_front(); // 弹出队头

        // 如果队列非空，且当前元素比队尾更小更优越
        while (!dq.empty() && a[i] <= a[dq.back()])
            dq.pop_back(); // 弹出队尾

        dq.push_back(i); // 当前元素下标入队尾
        // 此时队头为最小值

        // 前几次时还没有形成大小为 k 的窗口，形成后队头即为最小值
        if (i >= k - 1)
            cout << a[dq.front()] << ' ';
    }
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T = 1;
    // cin >> T;
    while (T--)
        solve();
    return 0;
}

单调栈

例-单调栈

例-求和

单调队列

例-滑动窗口

页底评论