【Day_02 0419】排序子序列

排序子序列

题目来源

牛客网：排序子序列

题目描述

牛牛定义排序子序列为一个数组中一段连续的子序列,并且这段子序列是非递增或者非递减排序的。牛牛有一个长度为n的整数数组A,他现在有一个任务是把数组A分为若干段排序子序列,牛牛想知道他最少可以把这个数组分为几段排序子序列.
如样例所示,牛牛可以把数组A划分为[1,2,3]和[2,2,1]两个排序子序列,至少需要划分为2个排序子序列,所以输出2

输入描述

输入的第一行为一个正整数n(1 ≤ n ≤ 10^5)
第二行包括n个整数A_i(1 ≤ A_i ≤ 10^9),表示数组A的每个数字。

输出描述

输出一个整数表示牛牛可以将A最少划分为多少段排序子序列

示例1

输入

6
1 2 3 2 2 1

输出

2

思路分析

• 非递增非递减序列，与递增递减序列的区别是可以有值相等的情况出现，如1、2、2、3、5，非递减原理相同
• 大循环条件为数组不越界
• 循环内部根据当前元素与下一个元素比较的结果分为三种情况，大于、小于、等于
• 因为可能连续几个元素都是升序或者降序，所以每个if分支内部用while进行判断，直到升序或者降序发生改变，每改变一次，子序列数目加1
• 当内部while条件不成立跳出内部循环后，要给j再加1，进入下一个子序列
• 为了避免数组越界，为数组后面加一个元素0，因为所有数都是正整数，所以加0不影响最终结果

代码展示

#include<iostream>
#include<vector>

using namespace std;
int main()
{
    
    int n = 0;
    vector<int> v;
    while (cin >> n)
    {
    
        //防止越界
        v.resize(n + 1);
        v[n] = 0;
        for (int i = 0; i < n; i++)
        {
    
            cin >> v[i];
        }
        int j = 0;
        int count = 0;
        while (j < n)
        {
    
            if (v[j] > v[j + 1])
            {
    
                //内部循环表示一个子序列
                while ((v[j] >= v[j + 1]) && j < n)
                {
    
                    j++;
                }
                count++;//内部循环结束,子序列数目加1
                j++;//j+1进入下一个子序列
            }
            else if (v[j] < v[j + 1])
            {
    
                while ((v[j] <= v[j + 1]) && j < n)
                {
    
                    j++;
                }
                count++;
                j++;
            }
            else
            {
    
                j++;
            }
        }
        cout << count;
    }
    return 0;
}