单调栈的平替算法

XGTD · 2024-11-25 12:00:36 · 算法·理论

我好像发现了一个能代替单调栈功能的算法。 ~~我估计99%的可能性要么已经有别人发现了， 要么复杂度不对~~，但是毕竟一个蒟蒻第一次自己发明一个算法还是想分享一下的。

算法目的： 给定一个数组a， 对于每一个i，找到最小的j使得j>i且a[j]>a[i]。

题目：P5788, https://www.luogu.com.cn/problem/P5788

算法过程十分简单智障：

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

正确性证明：

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

时间复杂度证明:

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

核心代码：

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单调栈模板题上过了，但是很有可能是因为我谷数据太仁慈。

附加功能：

同时这个算法似乎可以实现一个单调栈没有的功能：对每一个i,线性的找i后面第一个比a[i]大至少2的j。

算法过程和之前类似，只不过需要用到第一步算出来的l数组，判断三种情况，a[i + 1] - a[i] \geq 2, a[i + 1] - a[i] = 1,和a[i + 1] \leq a[i]. 第一种情况l2[i] = i + 1,第二种，l2[i] = l[i + 1],第三种和之前类似处理，只不过过程中还要判断a[j]是否比a[i]大1，如果是，l2[i] = l[j]。

正确性和复杂度可以用相似的方法证明。

本蒟蒻第一次发博客文章，算法简陋且大概率完全错误望各大佬勿喷。