题目描述

难度分:$1700$

输入$n(1 \leq n \leq 2 \times 10^5)$和长为$n$的双端队列$a(1 \leq a[i] \leq 2 \times 10^5)$。

每次操作，弹出$a$的队首或队尾。

从第二次操作开始，弹出的数字必须严格大于上一次弹出的数字。

输出最多可以弹出多少个数字，以及操作序列（队首为L，队尾为R）。

输入样例$1$

5
1 2 4 3 2

输出样例$1$

4
LRRR

输入样例$2$

7
1 3 5 6 5 4 2

输出样例$2$

6
LRLRRR

输入样例$3$

3
2 2 2

输出样例$3$

1
R

输入样例$4$

4
1 2 4 3

输出样例$4$

4
LLRR

算法

贪心模拟

这个题比较容易发现的是，如果队头元素更小就弹出队头，队尾元素更小就弹出队尾。而如果相等的话，假设弹出的是队头，由于弹出序列必须严格递增，队尾的元素不再有弹出的机会，要弹出只能不停地从队头弹出。同理，如果弹出的是队尾，那后续只能不停从队尾弹出，因此只要看队头和队尾哪边能延续更长的递增长度即可。

复杂度分析

时间复杂度

用相对双指针来模拟队头和队尾的弹出，时间复杂度是$O(n)$的。

空间复杂度

除了输入的数组之外，仅使用了有限几个变量，额外空间复杂度为$O(1)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>

using namespace std;
const int N = 200010;
int n, a[N];

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    int pre = 0, l = 1, r = n;
    string ans;
    while(l <= r && (a[l] > pre || a[r] > pre)) {
        bool isR = a[l] <= pre || (a[r] > pre && a[l] > a[r]);
        if(a[l] == a[r]) {
            int ll = l + 1, rr = r - 1;
            while(ll < r && a[ll] > a[ll - 1]) {
                ll++;
            }
            while(rr > l && a[rr + 1] < a[rr]) {
                rr--;
            }
            isR = r - rr > ll - l;
        }
        if(isR) {
            ans.push_back('R');
            pre = a[r--];
        }else {
            ans.push_back('L');
            pre = a[l++];
        }
    }
    cout << ans.size() << endl;
    cout << ans << endl;
    return 0;
}