求解代码
main 方法
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
|
public static int MAXN = 1000001;
public static int[] arr = new int[MAXN];
public static int[] stack = new int[MAXN];
public static int[][] ans = new int[MAXN][2];
public static int n,r;
public static void main(String[] args)throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StreamTokenizer in = new StreamTokenizer(br);
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
while(in.nextToken()!=StreamTokenizer.TT_EOF){
n = (int)in.nval;
for(int i=0;i<n;i++){
in.nextToken();
arr[i]=(int)in.nval;
}
compute();
for(int i=0;i<n;i++){
out.println(ans[i][0]+ " " + ans[i][1]);
}
}
out.flush();
out.close();
br.close();
}
|
compute 方法
整体来看就是三步走，先遍历，后清算，再修正。
用数组实现栈，变量r表示栈的使用情况，栈中存放的是数组的下标。
r=0时，即栈为空时，当前的遍历位置i直接入栈。
依次比较栈顶以及栈顶以下的元素对应的值和arr[i]的大小，如果大于等于arr[i]。
出栈后，如果栈为空，则左侧答案为-1，非空的话，左侧答案就是栈顶压着的那个元素；右侧答案就是让其出站的i位置。
如果遍历结束后，栈中还有元素，还需要依次弹出，也就是清算。
弹出元素的左侧答案，如果栈为空，则左侧答案为-1，非空的话，左侧答案就是栈顶压着的那个元素；右侧答案一律为-1。
考虑到存在相等的值，因此，还需要进行修正。
因为n-1位置右侧的答案一定是-1，所以无需修正。
如果右侧的答案不是-1，并且答案位置对应的值和当前位置对应的值相等，则将答案位置的右侧答案作为当前位置的右侧答案，这里可能有点拗口，但是仔细想想应该可以理解。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
public static void compute(){
r = 0;
int cur;
for(int i = 0;i<n;i++){
while(r>0&&arr[stack[r-1]]>=arr[i]){
cur = stack[--r];
ans[cur][0]=r>0?stack[r-1]:-1;
ans[cur][1]=i;
}
stack[r++]=i;
}
while(r>0){
cur = stack[--r];
ans[cur][0]=r>0?stack[r-1]:-1;
ans[cur][1]=-1;
}
for(int i=n-2;i>=0;i--){
if(ans[i][1]!=-1&&arr[ans[i][1]]==arr[i]){
ans[i][1]=ans[ans[i][1]][1];
}
}
}
|