ac

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

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 int mod=(int)Math.pow(10,9)+7;

    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[][] res = new int[n][2];
        for(int i=0;i<n;i++){
           res[i][0] = -1; // 左小
           res[i][1] = -1; // 右小
        }
        // 还是单调递增栈，不过相同的元素用了一个list结构
        ArrayDeque<List<Integer>> stack = new ArrayDeque<>();
        for(int i=0;i<n;i++){
            // 当前元素小于栈顶
            while (!stack.isEmpty() && arr[i] < arr[stack.peek().get(0)]){
                List<Integer> topList = stack.pop();
                // pop之后栈不为空，则可以求 topList 的左小
                int leftSmallest = -1;
                if(!stack.isEmpty()){
                    List<Integer> tmpTopList = stack.peek();
                    // 取最后一个index
                    leftSmallest = tmpTopList.get(tmpTopList.size() - 1);
                }
                for(int topVal: topList){
                    res[topVal][0] = leftSmallest; // 左小
                    res[topVal][1] = i; // 右小就是i了
                }
            }
            // 当前元素等于栈顶元素, 添加即可
            if(!stack.isEmpty() && arr[i] == arr[stack.peek().get(0)]){
                stack.peek().add(i);
            }else {
                // 栈为空，或者 大于栈顶了，要新开辟list了
                List<Integer> list = new ArrayList<>();
                list.add(i);
                stack.push(list);
            }
        }
        // 上面保持了栈如果不为空，一定是递增了，那么接着求左小即可
        while (!stack.isEmpty()){
            List<Integer> topList = stack.pop();
            int leftSmallest = -1;
            if(!stack.isEmpty()){
                List<Integer> tmpTopList = stack.peek();
                // 取最后一个index
                leftSmallest = tmpTopList.get(tmpTopList.size() - 1);
            }
            for(int topVal: topList){
                res[topVal][0] = leftSmallest; // 左小
            }
        }
        // 打印结果
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
//            System.out.println(res[i][0] + " " + res[i][1]);
            sb.append(res[i][0] + " " + res[i][1] + "\n");
        }
        System.out.print(sb.toString());
    }

}
/*
7
3 4 1 5 6 2 7

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

*/