专栏文章

单调栈的平替算法

XXGTD
算法·理论参与者 2已保存评论 2

文章操作

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

当前评论
2 条
当前快照
1 份
快照标识符
@mir05ca6
此快照首次捕获于
2025/12/04 13:35
3 个月前
此快照最后确认于
2025/12/04 13:35
3 个月前
查看原文
我好像发现了一个能代替单调栈功能的算法。 我估计99%的可能性要么已经有别人发现了， 要么复杂度不对，但是毕竟一个蒟蒻第一次自己发明一个算法还是想分享一下的。
算法目的： 给定一个数组aa， 对于每一个ii，找到最小的jj使得j>ij>i且a[j]>a[i]。a[j]>a[i]。
题目：P5788, https://www.luogu.com.cn/problem/P5788

算法过程十分简单智障：

维护ll, l[i]l[i]表示ii的答案。从后往前遍历，如果a[i]<a[i+1]a[i]<a[i+1],自然l[i]=i+1l[i]=i+1,否则对于一个j=l[i+1]j = l[i+1], while j≠0,j \neq 0,且 a[j]≤a[i]a[j]\leq a[i], j=l[j]j = l[j]. while循环结束时的jj即为l[i]l[i]

正确性证明：

首先第一种情况显然，如果a[i]<a[i+1]a[i]<a[i+1],自然l[i]=i+1l[i]=i+1. 第二种情况:对于每一个jj, 既然a[j]a[j] 已经 ≤a[i]\leq a[i]了，那jj到l[j]l[j]之间也绝不会出现大于a[i]a[i]的，我们就可以直接跳过。

时间复杂度证明:

由于每个jj除非作为某个ii的答案，否则只会被遍历一遍，因此复杂度O(n),与单调栈一样。

核心代码：

CPP
for(int i = n; i >= 1; i--){
	if(a[i] < a[i + 1])l[i] = i + 1;
	else{
		int j = l[i + 1];
		while(j != 0 && a[j] <= a[i]){
			j = l[j];
		}
		l[i] = j;
	}
}
for(int i = 1; i <= n; i++)cout<<l[i]<<" ";
我交到洛谷p5788单调栈模板题上过了，但是很有可能是因为我谷数据太仁慈。

附加功能：

同时这个算法似乎可以实现一个单调栈没有的功能：对每一个ii,线性的找ii后面第一个比a[i]a[i]大至少2的jj。
算法过程和之前类似，只不过需要用到第一步算出来的ll数组，判断三种情况，a[i+1]−a[i]≥2,a[i+1]−a[i]=1,a[i + 1] - a[i] \geq 2, a[i + 1] - a[i] = 1,和a[i+1]≤a[i]a[i + 1] \leq a[i]. 第一种情况l2[i]=i+1l2[i] = i + 1,第二种，l2[i]=l[i+1]l2[i] = l[i + 1],第三种和之前类似处理，只不过过程中还要判断a[j]a[j]是否比a[i]a[i]大11，如果是，l2[i]=l[j]l2[i] = l[j]。
正确性和复杂度可以用相似的方法证明。
本蒟蒻第一次发博客文章，算法简陋且大概率完全错误望各大佬勿喷。

评论

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

正在加载评论...