问题描述
给定一个长度为 NN 的序列 aa。
第一行输出每个数字其左边第一个比其大的数字，不存在则输出 -1。
第二行输出每个数字其右边第一个比其大的数字，不存在则输出 -1。
第三行输出每个数字其左边第一个比其小的数字，不存在则输出 -1。
第四行输出每个数字其右边第一个比其小的数字，不存在则输出 -1。
update：本题数据于 2025-01-13 加强至 2×1052×105，以杜绝暴力通过。
输入格式
第一行输入一个正整数 NN。(1≤N≤2×105)(1≤N≤2×105)
第二行输入 NN 个正整数，表示序列 aa。(1≤ai≤105,1≤i≤N)(1≤a**i≤105,1≤i≤N)
输出格式
第一行输出每个数字其左边第一个比其大的数字，不存在则输出 -1。
第二行输出每个数字其右边第一个比其大的数字，不存在则输出 -1。
第三行输出每个数字其左边第一个比其小的数字，不存在则输出 -1。
第四行输出每个数字其右边第一个比其小的数字，不存在则输出 -1。
样例输入
5
4 3 2 1 5
样例输出
-1 4 3 2 -1
5 5 5 5 -1
-1 -1 -1 -1 1
3 2 1 -1 -1
import java.util.*;
public class Main {
public static void main(String[] args) {
Deque<Integer> stack =new ArrayDeque<>();//使用双端队列，实现单调栈
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int[] array = new int[n];
for(int i=0;i<n;i++) {
array[i] = scan.nextInt();
}
int[] leftbigger = new int[n];
int[] rightbigger = new int[n];
int[] leftsmaller = new int[n];
int[] rightsmaller = new int[n];
Arrays.fill(leftbigger,-1);
Arrays.fill(rightbigger,-1);
Arrays.fill(leftsmaller,-1);
Arrays.fill(rightsmaller,-1);
for(int i=0;i<n;i++) {
while(!stack.isEmpty() && array[stack.peek()]<=array[i]){//保证stack里存的是大的，不是就要pop出来。
stack.pop();
}
if(!stack.isEmpty()) {
leftbigger[i] = array[stack.peek()];
}
stack.push(i);
}
stack.clear();
for(int i=n-1;i>=0;i--) {
while(!stack.isEmpty()&&array[stack.peek()]<=array[i]){//保证stack里存的是大的，不是就要pop出来。
stack.pop();
}
if(!stack.isEmpty()) {
rightbigger[i] = array[stack.peek()];
}
stack.push(i);
}
stack.clear();
for(int i=0;i<n;i++) {
while(!stack.isEmpty()&&array[stack.peek()]>=array[i]){//保证stack里存的是小的，不是就要pop出来。
stack.pop();
}
//刚开始栈为空
if(!stack.isEmpty()) {
leftsmaller[i] = array[stack.peek()];
}
stack.push(i);
}
stack.clear();
for(int i=n-1;i>=0;i--) {
while(!stack.isEmpty()&&array[stack.peek()]>=array[i]){//保证stack里存的是xiao的，不是就要pop出来。
stack.pop();
}
if(!stack.isEmpty()) {
rightsmaller[i] = array[stack.peek()];
}
stack.push(i);
}
stack.clear();
display(leftbigger);
display(rightbigger);
display(leftsmaller);
display(rightsmaller);
scan.close();
}
private static void display(int[] array) {
for(int i=0;i<array.length;i++) {
System.out.print(array[i]+" ");
}
System.out.println();
}
}