题目描述
给定一个长度为N的整数数列,输出每个数左边第一个比它小的数,如果不存在则输出-1。
输入格式
第一行包含整数N,表示数列长度。
第二行包含N个整数,表示整数数列。
输出格式
共一行,包含N个整数,其中第i个数表示第i个数的左边第一个比它小的数,如果不存在则输出-1。
数据范围
1 ≤N ≤ 105
1 ≤ 数列中元素 ≤ 109
输入样例
5
3 4 2 7 5
输出样例
-1 3 -1 2 2
单调栈
解题思路
给定我们一个序列,我们需要找到第i个数左边第一个比它小的数.
我们可以把i左边所以数存进栈中,每次从栈顶开始找,直至找到第一个比第i小的数.暴力大法好!
找到第一个比i小的数,通过这个我们可以挖掘出一些性质:
假设我们有一个数列:a1,a2,a3,a4,…ai
我们要找ai左边第一个小于ai的数,如果a2 > a4,那么a2是不是就永远不会被当做答案被输出
因为a4比a2小,而且在a2的后面,离ai更近
那么a4后面所有数的左边第一个最小的数再怎么说也不可能会是a2,那么a2是不是可以删掉?
通过这一性质,我们可以在每个数入栈时,进行比较,如果ax < ay,并且ax在ay左边,那么ay就可以删掉
只要满足这样的关系,我们就可以把前面的数删除,那么剩下的数就是单调的了.
实现:
我们用tt来维护栈,每次读入一个数x,如果栈是不空的,并且stk[tt] >= x,那么tt- -
然后判断,如果栈为空,则说明不存在,输出-1,不为空,则输出栈顶元素
参考文献
算法基础课
C++ 代码
#include<iostream>
using namespace std;
const int N = 100010;
int n, stk[N], tt;
int main()
{
cin >> n;
for(int i = 0; i < n; i ++)
{
int x;
cin >> x;
while(tt && stk[tt] >= x) tt --;
if(tt)cout << stk[tt] << ' ';
else cout << "-1 ";
//不要忘记把x入栈
stk[ ++ tt] = x;
}
return 0;
}
java代码
import java.util.Scanner;
public class Main{
static int[] stk=new int[100010];
static int tt;
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
for(int i=0;i<n;i++)
{
int x=sc.nextInt();
while(tt>0 && stk[tt]>=x) tt--;
if(tt>0) System.out.print(stk[tt]+" ");
else System.out.print("-1 ");
stk[++tt]=x;
}
}
}