单调栈

                     

贡献者: 有机物

预备知识 栈

   单调栈内部的元素都是单调递增或者递减的。单调栈处理问题的思想就是及时排除不可能的答案,从而可以更高效的求出答案

   单调栈可以解决的问题很少,经典问题就是用 $O(n)$ 的时间复杂度处理这么一类问题:求出每个数左/右边第一个比它小/大的数。

   我们就用:求出每个数左边第一个比它小的数,如果没有输出 $-1$。这个问题来讲解。

   举个例子: 输入:3 4 2 7 9,输出:-1 3 -1 2 2

   先想一下朴素算法怎么做: 两重循环来枚举,第一重循环枚举每个数 $a_i$,第二重循环从 $a_i$ 往左枚举每个数,直到找到第一个比 $a_i$ 小的数为止。

// 朴素算法的代码
cout << -1 << ' ';   // 第一个数的左边肯定没有比他小的数,所以先输出 -1
bool res = true;
for (int i = 0; i < n; i ++ ) {
    for (int j = i - 1; j >= 0; j -- )
        if (a[i] > a[j])
        {
            cout << a[j] << ' ';
            res = true;
            break;
        } else res = 0;
    
    if (!res) cout << -1 << ' ';
}

   上面的代码的时间复杂度显然是 $O(n^2)$ 的,我们来分析一下枚举的过程有没有什么性质,是不是有些元素是不是永远不会作为答案输出。 如果在枚举的过程中发现了这样一对数:$a_i \geqslant a_j, i < j$,那显然 $a_i$ 永远不会作为答案输出。因为 $a_j$ 比 $a_i$ 小,且比 $a_j$ 靠前,所以我们就可以用一个栈来维护 $a_i$ 左边的数,如果发现栈顶元素大于等于要插入的数 $x$,那么就可以把栈顶元素删了,我们就可以以一直删,直到发现了栈顶元素小于 $x$,那么栈顶元素就是答案,这样栈内的元素也就单调递减了。

// 单调栈代码
cin >> n;
while (n -- )
{
    int x;
    cin >> x;
    while (tt && stk[tt] >= x) tt -- ;  // 只要栈不为空且栈顶元素大于要插入的数 x,那么就删除栈顶元素
    if (!tt) printf("-1 ");             // 如果栈位空,则没有比该元素小的值
    else printf("%d ", stk[tt]);        // 栈顶元素就是左侧第一个比它小的元素
    stk[ ++ tt] = x;
}
// C++ STL

int n;
scanf("%d", &n);

stack<int> st;
while (n -- )
{
    int x;
    cin >> x;
    while (st.size() != 0 && st.top() >= x) st.pop();
    if (st.size() != 0) cout << st.top() << ' ';
    else cout << "-1" << ' ';
    st.push(x);
}

   图示

                     

© 小时科技 保留一切权利