【刷题记录】排列子序列

---

1️⃣题目

• 题目链接：排列子序列

⭕注意：题目中的关键信息 ——子序列是连续且非递增或非递减的、最少分为多少组。

---

2️⃣思路

若有一个序列a如下：

int a[] = {1,2,3,6,5,4,0,1};
1

根据题意，我们要把该序列分成以下几组，得出组数

当然也可能会有如下情况，子序列中有重复项，这是我们需要特殊注意的点：

💡总体思路：定义一个计数变量cnt和一个标志变量flag，flag为1时表示当前子序列为非递减序列，为0时表示当前子序列为非递增序列。遍历数组，判断当前数组元素是否满足flag标识的序列状态，若不满足，则cnt加1（当前元素前面的序列就是一段排序子序列），然后更新flag。重复上述过程，最终就能得到最少的排序子序列组数。

⭕更新flag的过程要尤其注意，flag的值需根据每个子序列前两个不同的元素来判断，由于每个子序列并不是单纯的递增或递减，可能包含相邻重复的数，因此我们需要去重后才能判断flag的更新值。

就像这个序列：
2222222222222222222222222210
我们需要用元素2和1来判断出它是非递增序列。

---

3️⃣代码分析

💬代码如下

时间复杂度：O(N)
空间复杂度：O(1)

#include 

using namespace std;

int find_next(long long* a,long long n,int i)
{
    // 去重，找到下一个不一样的
    int j = i+1;
    while(j < n && a[j] == a[i])
    {
        ++j;
    }
    return j;
}

int main()
{
    // 输入
    long long n = 0;
    cin >> n;
    long long a[n];
    for(size_t i = 0;i<n;++i)
    {
        cin >> a[i];
    }
   
    // 设置第一个子序列的flag值，1是非递减，0是非递增
    int next = find_next(a,n,0); // next表示当前数组位置去重后的下一位置
    int flag = 1; // 假设第一个子序列的flag为1
    if(next < n && a[next] < a[0])
    {
        flag = 0; // 不满足，则置0
    }
    
    long long cnt = 0;
    for(size_t i = next;i<n;++i)
    {
        if(flag == 1 && a[i] < a[i-1]) // 前面的序列是非递减序列
        {
            ++cnt;
            // 更新flag
            next = find_next(a,n,i);
            if(next < n && a[next] < a[i])
            {
                flag = 0;
            }
            i = next; // 下一次循环便跳过了当前子序列的前两个元素
        }
        else if(flag == 0 && a[i] > a[i-1]) // 前面的序列是非递增序列
        {
            ++cnt;
            // 更新flag
            next = find_next(a,n,i);
            if(next < n && a[next] > a[i])
            {
                flag = 1;
            }
            i = next;
        }
    }
    //最后的结果是cnt+1，因为最后一个子序列在循环中没有被计入
    cout << cnt+1 << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64