C++ 双向链表求解排列中比当前位置元素大的第一个位置

#include

using namespace std;

const int N = 100010; int n; int L[N], R[N], a[N], q[N];

int main() { cin >> n; for (int i = 1; i <= n; ++i) { int x; cin >> x; a[i] = x; }

for (int i = 1; i <= n; ++i) {
    R[i] = i + 1;
    L[i] = i - 1;
}

for (int i = n; i >= 1; --i) {
    int j = R[i];
    while (j <= n && a[j] <= a[i]) {
        j = R[j];
    }
    q[i] = j;
    R[L[i]] = R[i];
    L[R[i]] = L[i];
}

for (int i = 1; i <= n; ++i) {
    cout << q[i] << ' '; 
}

cout << endl;
return 0;

}