单调栈结构进阶问题_给定一个长度为 n 的可能含有重复值的数组 arr ,找到每一个 i 位置左边和右边离 i

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

• **与上一个单调栈问题一样。只不过这次在单调栈中存的不是数字。而是数组，其具体代码如下所示：在牛客上跑了一下只有75%；

import java.util.*;
import java.util.Arrays;
public class Main{
    public static void main(String [] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int [] arr = new int[n];
        for(int i=0;i<n;i++){
            arr[i] = sc.nextInt();
        }
        int [] [] res = getRes(n,arr);
        for(int i=0;i<n;i++){
            System.out.println(res[i][0]+" "+res[i][1]);
        }
    }
    
    public static int[][] getRes(int n, int[] arr){
        int [][] res = new int[n][2];
        Stack<List<Integer>> stack = new Stack<>();
        for(int i=0;i<n;i++){
            while(!stack.isEmpty() && arr[i]<arr[stack.peek().get(0)]){
                List<Integer> temp = stack.pop();
                int left = stack.isEmpty()? -1 : stack.peek().get(stack.peek().size()-1);
                for(Integer ind: temp){
                    res[ind][0] = left;
                    res[ind][1] = i;
                }
            }
            if(!stack.isEmpty()&& arr[i]==arr[stack.peek().get(0)]){
                stack.peek().add(Integer.valueOf(i));
            }else{
                ArrayList<Integer> list = new ArrayList<>();
                list.add(i);
                stack.push(list);
            }
        }
        while(!stack.isEmpty()){
            List<Integer> help = stack.pop();
            int left = stack.isEmpty()?-1:stack.peek().get(stack.peek().size()-1);
            for(Integer temp:help){
                res[temp][0] = left;
                res[temp][1] = -1;
            }
        }
        return res;
        
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48