题目描述

难度分:$1600$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的字符串长度之和$\leq 2 \times 10^5$。
每组数据长度$\leq 2 \times 10^5$的字符串$s$，只包含+，-，1，0四种字符。

一开始你有一个空栈$t$。
从左到右遍历$s$：

• 遇到+，入栈一个元素，大小未知。
• 遇到-，弹出栈顶元素，输入保证此时栈非空。
• 遇到1，说明此时从栈底到栈顶，一定是递增的，即一定满足$t[0] \leq t[1] \leq…$
• 遇到0，说明此时从栈底到栈顶，一定不是递增的，即一定不满足$t[0] \leq t[1] \leq…$

如果1和0的描述一定矛盾，输出NO，否则输出YES。
注：大小不足$2$的栈是递增的。

输入样例

7
++1
+++1--0
+0
0
++0-+1-+0
++0+-1+-0
+1-+0

输出

YES
NO
NO
NO
YES
NO
NO

算法

贪心

维护三个变量，序列长度$len$，已经排好序的最后一个位置$finish\_sort$，打乱顺序的第一个位置$unfinish\_sort$。这里可以采取贪心策略：为了能使无序最快地变回有序，我们只对有序的最后一个元素进行改动使得有序变成无序，这样只需要弹出这个元素，序列就立马会变成有序。初始情况下，$len=finish\_sort=unfinish\_sort=0$。

1. 追加数字时只需要自增$len$。
2. 弹出数字时自减$len$，此时如果$len \lt finish\_sort$，就要让有序的最后一个位置往前推，令$finish\_sort=len$。如果$len \lt unfinish\_sort$，就不存在无序了，令$unfinish\_sort=0$。
3. 在查询时，如果$s[i]=1$，$unfinish\_sort$必须为$0$，否则就矛盾，不矛盾就令$finish\_sort=len$。如果$s[i]=0$，$len$必须大于等于$2$，且不能等于$finish\_sort$（否则说明此时是有序的），若不满足就矛盾。没有矛盾的话就令$unfinish\_sort=len$。

复杂度分析

时间复杂度

在整个算法过程只遍历了一遍$s$串，时间复杂度是$O(n)$的。

空间复杂度

除去输入的$s$串所占空间，在整个算法过程中只使用了有限几个变量，额外空间复杂度是$O(1)$的。

C++ 代码

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

using namespace std;

const int N = 200010;
int t;
char s[N];

int main() {
    scanf("%d", &t);
    while(t--) {
        scanf("%s", s + 1);
        int n = strlen(s + 1);
        int len = 0, finish_sort = 0, unfinish_sort = 0;
        bool flag = true;
        for(int i = 1; i <= n; i++) {
            if(s[i] == '+') {
                len++;
            }else if(s[i] == '-') {
                len--;
                if(len < finish_sort) {
                    finish_sort = len;
                }
                if(len < unfinish_sort) {
                    unfinish_sort = 0;
                }
            }else {
                if(s[i] == '1') {
                    if(unfinish_sort) {
                        flag = false;
                        break;
                    }
                    finish_sort = len;
                }else {
                    if(len == finish_sort || len < 2) {
                        flag = false;
                        break;
                    }
                    if(unfinish_sort == 0) {
                        unfinish_sort = len;
                    }
                }
            }
        }
        if(flag) puts("YES");
        else puts("NO");
    }
    return 0;
}