单调栈
问题描述
给定一个长度为 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();}}
