专栏文章

单调栈&单调队列

LLQ_Q
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipu4cvg
此快照首次捕获于
2025/12/03 17:58
3 个月前
此快照最后确认于
2025/12/03 17:58
3 个月前
查看原文

单调栈

一.定义及概述

1.定义：

单调栈是一种内部元素具有单调性的栈。

1.概述：

利用出栈进栈的特性（入栈放最后，出栈出最后）来维护栈的单调性，利用该优化算法可以将 O(n^2) 的时间复杂的问题转化为 O(n) 。

1.适用场景

  • 求某个区间（无长度限制）的最值。

二.单调栈的适用问题特征

1.目标为值的个数

  • 在区间中某数的前(或后)的无长度限制区间存在多少个值比该数满足一定大小关系的的。
  • 典型问题
    • 区间 （无长度限制的） 内满足一定数量关系 (如：大于，小于等) 的值的总个数

三.单调栈的核心优化原理

同过入栈出栈的方式维护单调栈，利用以下特征将复杂度 O(n^2) 转化为 O(n)

1. 栈内单调性与不可逆性

  • 入栈： 保证于栈顶满足规定的数量关系
  • 出栈： 一直出栈直到满足入栈条件
  • 避免重复遍历： 单向出入栈，跳过一定满足条件的值，以免重复比较。

2.单向性

每个元素最多入一次出一次，复杂度是 O(2n)->O(n)

四.单调栈的基本模型

CPP
int num[MAXN]; //数列的存储 
stack<int>st; //单调栈用于存储下标 
int ans=0; //答案记录 
for(int i=1;i<=n;i++){
	//维护单调栈 
	while(!st.empty()&&num[st.top()] /*数量关系的反*/ num[i]){
		st.pop(); 
	}
	ans+=st.size(); //增加前 1~i-1 个数中于 num[i] 满足数量关系的高斯 
	st.push(a[i]); //入栈 
}

五.典型例题分析

P2866 [USACO06NOV] Bad Hair Day S

问题描述

给定一个数列，定义其中的每一个元素 i ，从 i+1 到第一个比 i 的值大或等于的元素所选中的区间中的元素个数和

问题转化

将问题转化为对于每一个元素 i 在 1~i-1 中所有满足给定数量关系的反及比元素 i 小的元素个数和

单调栈策略

  • 维护一个单调栈，栈内满足单调递减
  • 核心操作 对于一个元素 i
    • 出栈： 栈顶小于等于 i
    • 入栈： 栈顶大于 i
  • 答案每次的增长值为：栈顶大于 i 时栈的长度

代码实现

CPP
#include<bits/stdc++.h>
using namespace std;
int n,t;
long long ans;
stack <int> a;
int main(){
  cin>>n;
  for (int i=1; i<=n; i++) {
  	cin>>t;
  	while (!a.empty()&&a.top()<=t)  
  		a.pop();
  	ans+=a.size();
  	a.push(t);
  }
  cout<<ans;
  return 0;
}
P8094 [USACO22JAN] Cow Frisbee S

问题描述

给定一个数列,给定每一个元素的值 h ,其中存在区间 [i,j] ,保证区间中，除左端点 i 和右端点 j 外所有的元素都小于 min(h [i],h[j]) 求所有满足该性质的区间的长度和

问题转化

固定右端点，求取所有满足条件的点

单调栈策略

  • 维护一个单调栈，栈内满足单调递减
  • 核心操作：
    • 出栈： 栈顶小于等于 i
    • 入栈： 栈顶大于 i
  • 答案统计： 所有被 出栈的元素 和 最后入栈时的前一个元素 都满足条件

代码实现

CPP
#include<bits/stdc++.h>
using namespace std;
int n;
long long ans=0;
stack<int>st;
stack<int>sum;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		long long h;
		scanf("%lld",&h);
		while(!st.empty()&&h>=st.top()){
			ans+=(i-sum.top()+1);
			st.pop();
			sum.pop();
		}
		if(!st.empty()) ans+=(i-sum.top()+1);
		st.push(h);
		sum.push(i);
	}
	printf("%lld",ans);
}

单调队列

1.定义：

单调栈是一种内部元素具有单调性的队列。

1.概述：

利用队列双端的特性（可出头可出尾）来维护队列的单调性，利用该优化算法可以将 O(n^2) 的时间复杂的问题转化为 O(n) 。

1.适用场景

  • 求某个区间（无长度限制）的最值。

  • 1.目标为值的个数

  • 在区间中某数的前(或后)的有长度限制区间存在多少个值与该数满足一定大小关系的。
  • 典型问题
    • 区间 （有长度限制） 内 最值 。

三.单调栈的核心优化原理

通过推出队头和压入或推出队尾的方式的方式维护单调队列，利用以下特征将复杂度 O(n^2) 转化为 O(n)

1. 队内单调性与不可逆性

  • 入队： 保证于队列尾满足规定的数量关系
  • 出队（尾）： 一直出队直到满足入队条件
  • 出队（首）： 推出所有不在区间范围内的数据
  • 避免重复遍历： 单向出入队列，跳过一定满足条件的值，以免重复比较。

2.单向性

每个元素最多入一次出一次，复杂度是 O(2n)->O(n)

代码实现

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...