ac

给定一个不含有重复值的数组 arr，找到每一个 i 位置左边和右边离 i 位置最近且值比 arr[i] 小的位置。返回所有位置相应的信息。

7
3 4 1 5 6 2 7

-1 2
0 2
-1 -1
2 5
3 5
2 -1
5 -1

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static Scanner sc = new Scanner(System.in);

    public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws Exception {
        int n = sc.nextInt();
        int[] arr = new int[n];
        for(int i=0;i<n;i++) {
            arr[i] = sc.nextInt();
        }
        int[][] ans = new int[n][2];
        // 保持单调递增， 存储元素的下标
        Stack<Integer> sta = new Stack<>();
        ans[0][0] = -1;
        sta.push(0);
        for(int i=1;i<n;i++){
            int topIndex = sta.peek();
            // 入栈，即得出当前入栈元素的左边距离小
            if(arr[i] > arr[topIndex]){
                sta.push(i);
                ans[i][0] = topIndex;
            }else {
                // 大于当前元素的出栈，即得出出栈元素的右边距离小
                while (arr[topIndex] > arr[i]){
                    ans[topIndex][1] = i;
                    sta.pop();
                    if(sta.isEmpty()){
                        // 如果栈为空了，说明当前元素是最小的，其没有左边距离小
                        ans[i][0] = -1;
                        break;
                    }
                    topIndex = sta.peek();
                }
                // 栈不空，则当前元素的左边距离小就是当前栈顶
                if(!sta.isEmpty()) {
                    ans[i][0] = topIndex;
                }
                sta.push(i);
            }
        }
        if(!sta.isEmpty()){
            int lastPop = sta.pop();
            ans[lastPop][1] = -1;
            while (!sta.isEmpty()){
                int curIndex = sta.pop();
                ans[lastPop][0] = curIndex;
                ans[curIndex][1] = -1;
                lastPop = curIndex;
            }
        }
        for(int i=0;i<n;i++){
            System.out.println(ans[i][0] + " " + ans[i][1]);
        }
    }

}
/*
7
3 4 1 5 6 2 7

-1 2
0 2
-1 -1
2 5
3 5
2 -1
5 -1

8
999072 975092 922857 952573 991873 995164 931056 822016

-1 1
-1 2
-1 7
2 6
3 6
4 6
2 7
-1 -1
 */