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

using System;
using System.Collections.Generic;
using System.IO;
public class Program {
    public static void Main() {
        StreamReader sr = new StreamReader(Console.OpenStandardInput());
        using(StreamWriter sw = new StreamWriter(Console.OpenStandardOutput())){

        string line = sr.ReadLine();
        int N = int.Parse(line);
        int[] arr = new int[N];
        int[][] ans = new int[N][];
        for (int i = 0 ; i < N; i++) {
            ans[i] = new int[2];
        }
        string[] tokens = sr.ReadLine().Split();
        for (int i = 0 ; i < N; i++) {
            arr[i] = int.Parse(tokens[i]);
        }
        Stack<List<int>> stack = new Stack<List<int>>();
        for (int i = 0 ; i < N; i++ ) {
            while (stack.Count != 0 && arr[ stack.Peek()[0] ] > arr[i]) {
                List<int> temp = stack.Pop();
                int right = i;
                int left = stack.Count == 0 ? -1 : stack.Peek()[stack.Peek().Count - 1];
                for (int j = 0 ; j < temp.Count; j++) {
                    ans[temp[j]][0] = left;
                    ans[temp[j]][1] = right;
                }
            }
            if (stack.Count != 0 && arr[stack.Peek()[0]] == arr[i]) {
                stack.Peek().Add(i);
            } else {
                stack.Push(new List<int>() {
                    i
                });
            }
        }
        while (stack.Count != 0) {
            List<int> temp = stack.Pop();
            int right = -1;
            int left = stack.Count == 0 ? -1 : stack.Peek()[stack.Peek().Count - 1];
            for (int j = 0 ; j < temp.Count; j++) {
                ans[temp[j]][0] = left;
                ans[temp[j]][1] = right;
            }
        }
        for(int i = 0 ; i < N ;i++){
            sw.WriteLine(ans[i][0] + " " + ans[i][1]);
        }
        }
    }
}