​排序子序列​​

牛牛定义排序子序列为一个数组中一段连续的子序列,并且这段子序列是非递增或者非递减排序的。牛牛有一个长度为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;
}