题目信息
题目描述
给定一个长度为 N
的整数数列,输出每个数左边第一个比它小的数,如果不存在则输出 -1
。
输入格式
第一行包含整数 N,表示数列长度。
第二行包含 N 个整数,表示整数数列。
输出格式
共一行,包含 N 个整数,其中第i个数表示第i个数的左边第一个比它小的数,如果不存在则输出 -1。
数据范围
1 ≤ N ≤ $10^5$
1 ≤ 数列中元素 ≤ $10^9$
输入样例
5
3 4 2 7 5
输出样例
-1 3 -1 2 2
题解
解题思路
本题是一个典型的 单调栈 题目,单调栈经常用来 找出每个数左边或者右边离它最近的比它大或者小的数。首先说一下暴力做法,暴力做法就是枚举每一位数,从该数向前找一下第一个比该数小的数然后输出,如果没有找到则输出 -1。该做法的时间复杂度为 O($n^2$),时间复杂度太高,会 TLE
。
使用单调栈的做法是先将该数左边的数存到栈中,当遍历到当前元素时判断一下栈是否为空,如果栈不为空,那么就判断一下当前的栈顶元素与该数的大小,只要当前的栈顶元素比该数大,那么就弹出栈顶元素,直到栈为空或者找到一个比当前数小的栈顶元素。因为每次都要输出左边第一个比当前数小的数,所以只要栈顶元素比当前的数大那么就不可能被输出,所以一直弹出比当前数大的数。然后再判断一下栈是否为空,如果栈为空说明该数左边没有比其小的数,此时输出 -1;如果栈不为空,那么直接输出栈顶元素即可。最后要将当前的数入栈,因为当前的数是比栈中元素都大的数,而且可能会是比下一个数左边第一个比它小的数。
这里有一个比较重要的点要说明一下,题目的数据范围为 1 ≤ N ≤ $10^5$,所以在解题时最好使用 scanf() 输入,用 printf() 输出
,如果用 cin 和 cout 所需的时间会更多,依旧可能会超时。所以当输入数据的规模超过 $10^5$ 时 最好使用 scanf() 输入,用 printf() 输出
。规模小于 $10^5$ 两者消耗的时间差不多,都可以使用。
解题代码
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;
}
未完待续,持续更新中……
个人博客:ACfun的blog 欢迎来访鸭!
本文题目讲解博客地址:AcWing 830. 单调栈