单调栈

文章目录

• 前言

• 一、单调栈

• 1.单调栈

• 2.AcWing 830. 单调栈

• 题目分析：

• AC代码

• 二、时间复杂度

前言

复习acwing算法基础课的内容，本篇为讲解基础算法：用数组模拟单调栈，关于时间复杂度：目前博主不太会计算，先鸽了，日后一定补上。

一、单调栈

1.单调栈

在单调栈中，元素都是按照从小到大排好序或者从大到小排好序的，关于用数组模拟栈见博客：用数组模拟栈，这里不做赘述，关于单调栈的应用和作用，我们由一道题目展开

2.AcWing 830. 单调栈

本题链接：AcWing 830. 单调栈

本博客给出本题截图：

题目分析：

本题使用的是用单调递增栈，当该元素可以入栈的时，栈顶元素就是它左侧第一个比它小的元素，即所求的值

接下来按照样例逐步分析：

3 4 2 7 5:

1.把3入栈，对应答案为-1

2.因为4 > 3，4入栈，输出3

3.因为2 < 4，4 出栈

4.因为2 < 3，3出栈

5. 把2入栈，对应答案为-1

6.因为7 > 2，把7入栈，对应答案为2

7.因为5 < 7，把7出栈

8.因为5 > 2，把5入栈，输出2

故最后答案输出为-1 3 -1 2 2

AC代码

#include <cstdio>
using namespace std;
const int N = 100010;
int st[N], tt;
int main()
{
    int n;
    scanf("%d", &n);
    while (n -- )
    {
        int x;
        scanf("%d", &x);
        while (x <= st[tt] && tt) tt --;
        if (tt == 0) printf("-1 ");
        else printf("%d ", st[tt]);            //注意是先输出栈顶元素，再把x加入到栈中
        st[ ++ tt ] = x;
    }
    return 0;
}

二、时间复杂度

关于单调栈的各操作时间复杂度以及证明，后续会给出详细的说明以及证明过程，目前先鸽了。