c++单调数据结构————单调栈，单调队列

目录

一，单调栈

二，单调队列

例题一(单调栈）：蓝桥杯官网——百亿富翁

题目描述

输入描述

输出描述

输入输出样例

示例 1

代码详解：

解释：计算 dpl 时 stk 的工作过程

例题二（单调队列）：蓝桥杯官网——分蛋糕

问题描述

输入格式

输出格式

样例输入

样例输出

代码详解：

注：本文所有题目均来自蓝桥杯官网公开真题，仅做算法学习，代码皆由本人做出来并附上解析！

一，单调栈

单调栈是一个时刻保证内部元素具有单调性质的栈，是一种线性结构。其单调特性使得处理一些问题变得高效，例如求某个点左侧或右侧第一个比它大的点的位置（类似于lower_bound）。

单调栈的核心思想是：在入栈时逐个删除所有 “更差的点”，保持单调性。单调栈一般可分为单调递减栈、单调递增栈、单调不减栈、单调不增栈，需要根据题意来确定。同时，用数组实现的单调栈会比用 STL 实现的更灵活，可以在里面进行二分，LIS（最长递增子序列（Longest Increasing Subsequence）） 的 O (nlogn) 算法就需要用到单调栈 + 二分。

二，单调队列

1. 基础定义：和单调栈思想类似，是基于 “双端队列” 的线性数据结构，内部元素保持单调性质。

2. 元素存储：大多时候队列中存储的是 “下标”，而非 “元素值”。

3. 核心逻辑：

   • 队头是 “最优的元素”，后面是候选元素；
   • 入队时会直接删除 “没有价值的元素”。

4. 适用场景：常用于处理固定长度的区间最值问题。

例题一(单调栈）：蓝桥杯官网——百亿富翁

题目描述

已知有一排楼房一共有 N 栋，编号分别为 1∼N，第 ii 栋的高度为 hi​。

好奇的小明想知道对于每栋楼，左边第一个比它高的楼房是哪个，右边第一个比它高的楼房是哪个（若不存在则输出 −1）。

输入描述

第 1 行输入一个整数 N，表示楼房的数量。

第 2 行输入 N 个整数（相邻整数用空格隔开），分别为 h1​,h2​,...,hN​，表示楼房的高度。

1≤N≤7×10^5，1≤hi​≤10^9。

输出描述

输出共两行。

第一行输出 N 个整数，表示每栋楼左边第一栋比自己高的楼的编号。

第二行输出 N 个整数，表示每栋楼右边第一栋比自己高的楼的编号。

输入输出样例

示例 1

输入：

5 3 1 2 5 4

输出：

-1 1 1 -1 4 4 3 4 -1 -1

代码详解：

#include <iostream> using namespace std; const int N=7e5+9; int a[N],stk[N],dpl[N],dpr[N],top; /* a[]存入原数组 stk[]存入元素编号，模拟一个特殊的栈，使得（a[stk[1]] > a[stk[2]] > ... > a[stk[top]]）（核心思想！） dpl[i]表示a[i]左边第一个大于a[i]的数的编号，没有就是-1 dpr[i]表示a[i]右边第一个大于a[i]的数的编号，没有就是-1 */ int main() { ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); int n;cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; //遍历左边 for(int i=1;i<=n;i++) { //注意：top的遍历方式是从上往下遍历栈（弹出栈顶元素）！ //从栈顶开始，若栈顶对应的a中的元素<=a[i]，就出栈，继续遍历栈顶下一个元素 //因为stk栈满足栈底到栈顶所对应的a[i]值依次减小，然而stk中存储的又必然是for循环已遍历的元素的下标 //所以要从上往下遍历，才能在栈中准确找到第一个大于a[i]的元素的下标，对应的就是a[i]左边第一个大于a[i] //的元素下标！ while(top&&a[stk[top]]<=a[i]) top--;//若top存在，就从栈顶往下遍历（top--） //看看有没有元素大于a[i],直到top=0（说明遍历所有都没有）或找到了大于a[i]的数 dpl[i]=top?stk[top]:-1;//若top不为0，说明在栈中有下标元素对应的a[]值大于a[i], //则输出stk[top]，否则输出-1 //编号入栈 stk[++top]=i; } top=0; //遍历右边 for(int i=n;i>=1;i--) { while(top&&a[stk[top]]<=a[i]) top--; dpr[i]=top?stk[top]:-1; stk[++top]=i; } for(int i=1;i<=n;i++) cout<<dpl[i]<<" "; cout<<'\n'; for(int i=1;i<=n;i++) cout<<dpr[i]<<" "; return 0; }

解释：计算 dpl 时 stk 的工作过程

dpl[i] 表示"a[i] 左边第一个比它大的元素的下标"，遍历方向是从左到右（i=1 到 i=5）。
初始状态：top=0（栈为空），stk 中没有元素。
第一步：i=1（a[1]=3）
栈为空（top=0），无需弹出元素。
dpl[1] = -1（左边没有元素）。
将 i=1 入栈：stk[1]=1，top=1。
此时栈中元素（下标）：[1]，对应 a 的值：[3]（单调递减）。
第二步：i=2（a[2]=1）
检查栈顶：a[stk[1]] = a[1] = 3，3 > 1（不满足「小于等于」），所以不弹出。
dpl[2] = stk[1] = 1（左边第一个更大元素是下标 1）。
将 i=2 入栈：stk[2]=2，top=2。
此时栈中元素：[1, 2]，对应 a 的值：[3, 1]（仍然单调递减）。
第三步：i=3（a[3]=4）
检查栈顶：a[stk[2]] = a[2] = 1，1 <= 4 -->弹出（top=1）。
再检查栈顶：a[stk[1]] = a[1] = 3，3 <= 4 -->弹出（top=0）。
栈为空，dpl[3] = -1（左边没有更大元素）。
将 i=3 入栈：stk[1]=3，top=1。
此时栈中元素：[3]，对应 a 的值：[4]（单调递减）。
第四步：i=4（a[4]=2）
检查栈顶：a[stk[1]] = a[3] = 4，4 > 2 --> 不弹出。
dpl[4] = stk[1] = 3（左边第一个更大元素是下标 3）。
将 i=4 入栈：stk[2]=4，top=2。
此时栈中元素：[3, 4]，对应 a 的值：[4, 2]（单调递减）。
第五步：i=5（a[5]=5）
检查栈顶：a[stk[2]] = a[4] = 2，2 <= 5 --> 弹出（top=1）。
再检查栈顶：a[stk[1]] = a[3] = 4，4 <= 5 --> 弹出（top=0）。
栈为空，dpl[5] = -1。
将 i=5 入栈：stk[1]=5，top=1。
此时栈中元素：[5]，对应 a 的值：[5]（单调递减）。

例题二（单调队列）：蓝桥杯官网——分蛋糕

问题描述

小蓝去蛋糕店，蛋糕店有 n 个蛋糕摆在一排，每个蛋糕都有一个高度 h[i]。小蓝想买 k 个蛋糕，但他只买符合以下要求的蛋糕：

1. 买的 k 个蛋糕必须连续摆放在一起。
2. k 个蛋糕中的最大值与最小值之差要小于等于 x。

现在小蓝想知道，他任选 k 个连续摆放的蛋糕，恰好符合他要求的概率是多少。

由于精度问题，你的输出需要对 998244353 取模。

输入格式

第一行输入三个整数 n,k,x，为题目所表述的含义。

第二行输入 n 个整数，表示每个蛋糕的高度。

输出格式

输出一个整数，表示小蓝愿意买的概率对 998244353 取模的结果。

样例输入

4 3 2 1 4 6 6

样例输出

499122177

代码详解：

#include <iostream> using namespace std; using ll=long long; const int N=1e5+9; ll a[N],q[N],mi[N],mx[N]; const ll p=998244353; /*给定数组 a（长度 n）、窗口长度 k、阈值 x： 求所有长度为 k 的滑动窗口的最小值（存入 mi 数组）和最大值（存入 mx 数组）； 统计满足 mx[i] - mi[i] ≤ x 的窗口数量 cnt； 计算 cnt / (n-k+1) 的值（模 998244353，除法通过逆元实现）并输出。 */ //为什么需要逆元？ //模运算中没有直接的除法，cnt / (n-k+1) mod p 等价于 cnt * inv(n-k+1) mod p（inv 是乘法逆元）； //费马小定理：若 p 是质数且 x 与 p 互质，则 x^(p-1) ≡ 1 mod p → x^(p-2) ≡ x^(-1) mod p（即逆元）。 ll qmi(ll a,ll b) { ll res=1;//永远不要忘记res初始化为1！！！ while(b) { if(b&1) res=res*a%p; a=a*a%p,b>>=1; } return res; } ll inv(ll x)//这里要返回ll！ { return qmi(x,p-2); } int main() { ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); int n,k,x;cin>>n>>k>>x; for(int i=1;i<=n;i++) cin>>a[i]; //开始队列操作： int hh=1,tt=0; //求固定区间的最小值mi[i] // mi[i] 表示：以i为 窗口右端点 的长度为k的窗口的最小值 for(int i=1;i<=n;i++) { //步骤1：弹出队头超出窗口范围的元素（维护窗口左边界） //窗口左边界 = i - k + 1（右端点i，长度k），队头下标 < 左边界 -> 无效，弹出 while(hh<=tt&&q[hh]<i-k+1) hh++; //步骤2：弹出队尾比当前元素大的元素（维护队列单调递增） //队列内下标对应的值要递增 -> 队尾值 > a[i] -> 队尾元素不可能是当前/后续窗口的最小值，直接弹出 while(hh<=tt && a[q[tt]]>a[i])tt--; //步骤3：当前下标入队（队尾） q[++tt]=i; //步骤4：记录当前窗口的最小值（队头就是最小值下标） mi[i]=a[q[hh]]; } //求固定区间的最大值 hh=1,tt=0; // 重置队列 // mx[i] 表示：以i为窗口右端点的长度为k的窗口的最大值 for(int i=1;i<=n;i++) { //步骤1：弹出队头超出窗口范围的元素（和求最小值逻辑一致） while(hh<=tt&&q[hh]<i-k+1) hh++; //步骤2：弹出队尾比当前元素小的元素（维护队列单调递减） //队列内下标对应的值要递减 ->队尾值 < a[i] ->队尾元素不可能是当前/后续窗口的最大值，直接弹出 while(hh<=tt && a[q[tt]]<a[i])tt--; //步骤3：当前下标入队 q[++tt]=i; //步骤4：记录当前窗口的最大值（队头就是最大值下标） mx[i]=a[q[hh]]; } int cnt=0; for(int i=k;i<=n;i++)if(mx[i]-mi[i]<=x)cnt++; cout<<cnt*inv(n-k+1)%p<<'\n'; /*总窗口数：n-k+1（比如 n=5,k=2 → 窗口数 = 4：[1,2],[2,3],[3,4],[4,5]）； 只有 i≥k 时，窗口才是完整的（左端点 ≥1），因此遍历 i 从 k 到 n； 最终结果取模：避免溢出，且符合算法题的模数要求。*/ return 0; }