题目描述
给定一个长度为N的整数数列,输出每个数左边第一个比它小的数,如果不存在则输出 −1。
输入格式
第一行包含整数 N,表示数列长度。
第二行包含 N个整数,表示整数数列。
输出格式
共一行,包含 N个整数,其中第 i个数表示第 i个数的左边第一个比它小的数,如果不存在则输出 −1。
数据范围
1≤N≤105
1≤数列中元素≤109
样例
输入样例:
5
3 4 2 7 5
输出样例:
-1 3 -1 2 2
思路
单调栈的问题,我们从左到右依次遍历,当我们遍历到a[i]时,如果a[i-1]这个位置的数字大于a[i],那么a[i]往后的数字 例如a[k]在向前找小于它的数字时,必定会到a[i]就停止,无需遍历在a[i]之前的所有元素,我们的想法是把数组内的元素尽量少,因为前面有一些是完全多余的。
打个比方 3 4 2 7 5
当我们在遍历到2时候 前面3 4都是大于它的 因此当7在遍历时 不会到达2往左的位置,此时,我们可以将3 4移出数组,5向左遍历时 同理,不会到达2左边的位置。
这个例子不够鲜明 那么请看 9 8 7 6 5 4 3 2 1
当我们遍历数组时 如果没有移除数这一项 那么当遍历到1时,它需要向左遍历到9 时间复杂度是比较高的,而当我们有移除操作时,当遍历到1,我们只需要比较1和2 因为2左边都是小于它的数字,如果一个数比2还要小,那么左边的数 一定都不符合要求。
因为涉及到数的删除操作,我用了模拟双链表来实现的单调栈这个功能。
首先,双链表具有从左从右遍历的功能,使用起来较为方便,并且移除数字的remove操作也较为简单。
关键代码如下:外层循环是从左到右遍历双链表,内层是从该结点的左边向左遍历
当遍历到小于它的数字时 循环停止 输出该数 否则 移除该结点 循环继续 等到循环结束时 还没找到 则输出-1
for(int i=r[0];i!=1;i=r[i]){
int j;
for(j=l[i];e[j]>=e[i]&&j!=0;j=l[j]){
remove(j);
}
if(j==0) System.out.print("-1 ");
else System.out.print(e[j]+" ");
}
参考文献
y总的双链表模板
时间复杂度
小于O(n²)
具体 Java 代码实现如下
import java.util.Scanner;
public class Main {
static int N=100010;
static int[] e=new int[N];
static int[] l=new int[N];
static int[] r=new int[N];
static int idx;
static void init(){
r[0]=1;
l[1]=0;
idx=2;
}
static void add (int k,int x){
e[idx]=x;
r[idx]=r[k];
l[idx]=k;
l[r[k]]=idx;
r[k]=idx;idx++;
}
static void remove(int k){
r[l[k]]=r[k];
l[r[k]]=l[k];
}
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
int n=input.nextInt();
init();
for(int i=1;i<=n;i++){
int x=input.nextInt();
add(l[1],x);
}
for(int i=r[0];i!=1;i=r[i]){
int j;
for(j=l[i];e[j]>=e[i]&&j!=0;j=l[j]){
remove(j);
}
if(j==0) System.out.print("-1 ");
else System.out.print(e[j]+" ");
}
}