AcWing 830. 单调栈

末蓝、 2022-10-24 13:24 161阅读 0赞

**上一篇博客：[AcWing 42. 栈的压入、弹出序列][AcWing 42.]**

>  写在前面：大家好！我是`AC-fun`,我的昵称来自两个单词`Accepted`和`fun`。我是一个热爱ACM的蒟蒻。如果博客中有不足或者的错误的地方欢迎在评论区或者私信我指正，感谢大家的不吝赐教。我的唯一博客更新地址是：[https://ac-fun.blog.csdn.net/][https_ac-fun.blog.csdn.net]。非常感谢大家的支持。一起加油，冲鸭！  
>  `用知识改变命运，用知识成就未来！加油 (ง •̀o•́)ง (ง •̀o•́)ง`

原题链接：[AcWing 830. 单调栈][AcWing 830.]

### 文章目录 ###

*  题目信息
 *   *  题目描述
     *  输入格式
     *  输出格式
     *  数据范围
     *  输入样例
     *  输出样例
 *  题解
 *   *  解题思路
     *  解题代码
     *   *  stack + cin + cout
         *  stack + scanf() + printf()
         *  数组模拟栈 + scanf() + printf()

# 题目信息 #

## 题目描述 ##

给定一个长度为 `N` 的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出 `-1`。

## 输入格式 ##

第一行包含整数 **N**，表示数列长度。

第二行包含 **N** 个整数，表示整数数列。

## 输出格式 ##

共一行，包含 **N** 个整数，其中第i个数表示第i个数的左边第一个比它小的数，如果不存在则输出 **-1**。

## 数据范围 ##

> 1 ≤ N ≤  1 0 5 10^5 105  
> 1 ≤ 数列中元素 ≤  1 0 9 10^9 109

## 输入样例 ##

> 5  
> 3 4 2 7 5

## 输出样例 ##

> \-1 3 -1 2 2

# 题解 #

## 解题思路 ##

本题是一个典型的 **单调栈** 题目，单调栈经常用来 找出每个数左边或者右边离它最近的比它大或者小的数。首先说一下暴力做法，暴力做法就是枚举每一位数，从该数向前找一下第一个比该数小的数然后输出，如果没有找到则输出 **-1**。该做法的时间复杂度为 **O( n 2 n^2 n2)**，时间复杂度太高，会 `TLE`。

使用单调栈的做法是先将该数左边的数存到栈中，当遍历到当前元素时判断一下栈是否为空，如果栈不为空，那么就判断一下当前的栈顶元素与该数的大小，只要当前的栈顶元素比该数大，那么就弹出栈顶元素，直到栈为空或者找到一个比当前数小的栈顶元素。因为每次都要输出左边第一个比当前数小的数，所以只要栈顶元素比当前的数大那么就不可能被输出，所以一直弹出比当前数大的数。然后再判断一下栈是否为空，如果栈为空说明该数左边没有比其小的数，此时输出 **-1**；如果栈不为空，那么直接输出栈顶元素即可。最后要将当前的数入栈，因为当前的数是比栈中元素都大的数，而且可能会是比下一个数左边第一个比它小的数。

这里有一个比较重要的点要说明一下，题目的数据范围为 **1 ≤ N ≤  1 0 5 10^5 105**，所以在解题时`最好使用 scanf() 输入，用 printf() 输出`，如果用 cin 和 cout 所需的时间会更多，可能会超时。所以当输入数据的规模超过  1 0 5 10^5 105 时 `最好使用 scanf() 输入，用 printf() 输出`。规模小于  1 0 5 10^5 105 两者消耗的时间差不多，都可以使用。

## 解题代码 ##

![解题方式以及消耗时间情况][20210130160715297.png]

### stack + cin + cout ###

#include<iostream>
    #include<stack>
    using namespace std;
    
    const int N = 100010;
    
    int main() { 
        stack<int> stk;
        int n;
        cin >> n;
        for (int i = 0; i < n; i++) { 
            int x;
            cin >> x;
            while (stk.size() && stk.top() >= x) stk.pop();
            if (stk.size()) cout << stk.top() << ' ';
            else cout << -1 << ' ';
            stk.push(x);
        }
        
        return 0;
    }

--------------------

### stack + scanf() + printf() ###

#include<iostream>
    #include<stack>
    using namespace std;
    
    const int N = 100010;
    
    int main() { 
        stack<int> stk;
        int n;
        cin >> n;
        for (int i = 0; i < n; i++) { 
            int x;
            scanf("%d", &x);
            while (stk.size() && stk.top() >= x) stk.pop();
            if (stk.size()) printf("%d ", stk.top());
            else printf("-1 ");
            stk.push(x);
        }
        
        return 0;
    }

--------------------

### 数组模拟栈 + scanf() + printf() ###

#include<iostream>
    #include<stack>
    using namespace std;
    
    const int N = 100010;
    int stk[N], top;
    
    int main() { 
        int n;
        cin >> n;
        for (int i = 0; i < n; i++) { 
            int x;
            scanf("%d", &x);
            while (top && stk[top] >= x) top--;
            if (top) printf("%d ", stk[top]);
            else printf("-1 ");
            stk[++top] = x;
        }
        
        return 0;
    }

--------------------

> 未完待续，持续更新中……  
> ![20210130161212665.png][]

[AcWing 42.]: https://ac-fun.blog.csdn.net/article/details/113193347
[https_ac-fun.blog.csdn.net]: https://ac-fun.blog.csdn.net/
[AcWing 830.]: https://www.acwing.com/problem/content/description/832/
[20210130160715297.png]: /images/20221024/63d1b3bc4db544afb64923f4018d2059.png
[20210130161212665.png]: /images/20221024/404604d7c8f34e7ea59f5a5df2f79b97.png