单调栈

贡献者：有机物

预备知识　栈

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

　　单调栈可以解决的问题很少，经典问题就是用 $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} ⩾ 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);
}

　　图示

致读者：小时百科一直以来坚持所有内容免费无广告，这导致我们处于严重的亏损状态。长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。因此，我们请求广大读者热心打赏 ，使网站得以健康发展。如果看到这条信息的每位读者能慷慨打赏 20 元，我们一周就能脱离亏损，并在接下来的一年里向所有读者继续免费提供优质内容。但遗憾的是只有不到 1% 的读者愿意捐款，他们的付出帮助了 99% 的读者免费获取知识，我们在此表示感谢。