题解 | #单调栈结构(进阶)#

参考左神的代码，使用两个栈，一个栈stack1是一个递增栈，并且里面可以存储重复值。另一个栈stack2是存储每一系列相同值的最后一个下标，用这种方式就可以区分左面小于当前值的下标是多少。

import java.util.*;

import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException{
        StreamTokenizer st = new StreamTokenizer(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        st.nextToken();
        int n = (int) st.nval;

        int[][] res = new int[n][2];
        int[] arr = new int[n];

        for (int i = 0; i < n; i++) {
            st.nextToken();
            arr[i] = (int) st.nval;
        }

        int[] stack1 = new int[n];
        int[] stack2 = new int[n];
        int stackSize1 = 0, stackSize2 = 0;

        for (int i = 0; i < n; i++) {
            while (stackSize1 != 0 && arr[stack1[stackSize1 - 1]] > arr[i]) {
                int cur = stack1[--stackSize1];
                res[cur][1] = i;
                int left = stackSize2 < 2 ? -1 : stack2[stackSize2 - 2];
                res[cur][0] = left;
                //得判断一下，弹出的这个栈顶和前一个元素是不是相同。 如果不同，stack2中的元素要减一个
                if (stackSize1 == 0 || arr[stack1[stackSize1 - 1]] != arr[cur]) {
                    stackSize2--;
                }
            }
            //至此，栈顶上比当前元素大的元素已经都弹出去了
            if (stackSize1 == 0 || arr[stack1[stackSize1 - 1]] != arr[i]) {
                //如果栈顶元素与当前的不同
                stack2[stackSize2++] = i;
                
            } else {
                //如果栈顶元素与当前的相同

                stack2[stackSize2 - 1] = i;
            }
            stack1[stackSize1++] = i;
        }
        while (stackSize1 != 0) {
            int cur = stack1[stackSize1 - 1];
            stackSize1--;
            res[cur][1] = -1;
            int left = stackSize2 < 2 ? -1 : stack2[stackSize2 - 2];
            res[cur][0] = left;
            if (stackSize1 == 0 || arr[stack1[stackSize1 - 1]] != arr[cur]) {
                //如果栈顶元素与当前的不同
                stackSize2--;
            }
        }

        for (int[] r : res) {
            sb.append(r[0]).append(' ').append(r[1]).append('\n');
        }
        System.out.print(sb.toString());
           
    }
}