​排序子序列​​

牛牛定义排序子序列为一个数组中一段连续的子序列,并且这段子序列是非递增或者非递减排序的。牛牛有一个长度为n的整数数组A,他现在有一个任务是把数组A分为若干段排序子序列,牛牛想知道他最少可以把这个数组分为几段排序子序列.

如样例所示,牛牛可以把数组A划分为[1,2,3]和[2,2,1]两个排序子序列,至少需要划分为2个排序子序列,所以输出2

试题来源: ​​排序子序列​​

#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n = 0;
cin >> n;
vector<int> v;
v.reserve(n + 1);
int ret = 0;
for (int i = 0; i < n; i++)
    {
cin >> v[i];
    }
// 这个的作用  
// 1.避免越界
// 2.避免 1 2 3 2 2 这种情况
v[n] = 0;

// 计数器 
int count = 0;
int i = 0; // 这个是一个循环
while (i < n)
    {
// 非递减序列
if (v[i] < v[i + 1])
        {
// 主意不能一直加 范围 i+1也会越界 我们 开辟 n+1个 解决了
while (i < n && v[i] <= v[i + 1])
            {
i++;
            }
count++;
i++;
        }
else if (v[i] == v[i + 1])
        {
i++;
        }
else
        {
while (i < n && v[i] >= v[i + 1])
            {
i++;
            }
count++;
i++;
        }
    }
cout << count << endl;
return 0;
}