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

//单调栈结构(进阶)
//https://www.nowcoder.com/practice/2a2c00e7a88a498693568cef63a4b7bb

#include<bits/stdc++.h>

using namespace std;

const int N = 1e6+10;

int arr[N];
int stk[N];
int ans[N][2];
int top=0;//栈顶
int n=0;//arr元素个数
int pop=0;//当前弹出的位置

void compute()
{
//一、入栈阶段：
    //遍历:严格大压小,将不合适的元素弹出占中，此时弹出的元素的左右答案已经找到，只剩下弹栈完后的栈中元素的左右答案还未找到
    for(int i=0 ; i<n ; i++)
    {
        //一阶弹栈：入栈时遇到小于或等于栈中元素时弹栈
        //弹栈可以结算答案
        while( (top > 0) && (arr[i] <= arr[stk[top-1]]) )
        {
            //将要弹栈的下标：pop
            pop = stk[--top];//当前要被弹出的元素下标
            //ans[pop][0]：结算左边 | ans[pop][1]：结算右边
            ans[pop][0] = top > 0 ? stk[top-1] : -1; //判断当前元素地下还有没有数
            ans[pop][1] = i;
        }
        //将大于等于当前元素的元素全部弹栈之后 , 将当前元素入栈
        stk[top++] = i;
    }

//二、弹栈阶段(二阶弹栈) 
    //清算阶段：将栈中的元素找到左右答案
    //将栈中的下标一次弹出
    while(top > 0) // top > 0 栈里有元素
    {
        pop = stk[--top];
        ans[pop][0] = top > 0 ? stk[top-1] : -1;
        ans[pop][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];
        }
    }
}

int main()
{
    scanf("%d" , &n);
    for(int i=0 ; i<n ; i++)
    {
        scanf("%d" , &arr[i]);
    }

    compute();

    for(int i=0 ; i<n ; i++)
    {
        printf("%d %d\n" , ans[i][0] , ans[i][1]);
    }

    return 0;
}