题解 | #单调栈结构，C++，含重复元素#

数组中含重复元素的情况下，寻找每个元素左边和右边比当前元素小的位置。
单调栈实现
思路：栈内元素是一个链表，用链表保存相同元素出现的所有位置，然后出栈的时候依次遍历每个位置。
实现：使用vector实现不定长的数组，取最后一个元素是back()操作

#include<stack>
#include<vector>
using namespace std;

int main(){
    int n;
    scanf("%d", &n);
    int nums[n];
    for(int i=0;i<n;i++){
        scanf("%d", &nums[i]);
    }
    int result[n][2];
    int L,R;
    stack<vector<int>>stk;
    
    for(int i=0;i<n;i++){
        while(!stk.empty() && nums[i]<nums[stk.top().back()]){
            vector<int>cur=stk.top();
            stk.pop();
            if(stk.empty()){
                L=-1;
            }
            else{
                L=stk.top().back();
            }
            R=i;
            //给相同的每个位置都赋值
            for(int j=0;j<cur.size();j++){
                result[cur[j]][0]=L;
                result[cur[j]][1]=R;
            }
        }
        if(!stk.empty() && nums[i]==nums[stk.top().back()]){
            stk.top().push_back(i);
        }
        else{
            vector<int>position;
            position.push_back(i);
            stk.push(position);
        }
    }
    while(!stk.empty()){
        vector<int>cur=stk.top();
        stk.pop();
        if(stk.empty()){
            L=-1;
        }
        else{
            L=stk.top().back();
        }
        R=-1;
        //给相同的每个位置都赋值
        for(int j=0;j<cur.size();j++){
            result[cur[j]][0]=L;
            result[cur[j]][1]=R;
        }
    }
    for(int i=0;i<n;i++){
        printf("%d %d\n",result[i][0], result[i][1]);
    }
    return 0;
}