链接：https://www.nowcoder.com/questionTerminal/2d3f6ddd82da445d804c95db22dcc471 来源：牛客网

题目描述

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

题目分析

暴力解法，不要把自己绕晕，一个一个遍历，当递增递减序列停止的时候count++。 注意为了避免a[i+1]的越界，我们在数组后加一个零，因为由题干可知，所有的数据都比0大且0在第n个位置，所以不会对结果有影响。

#include<iostream>
#include<vector>
using namespace std;
int main()
{
    int n;
    cin>>n;
    vector<int> a;
    a.resize(n+1);
    for(auto& e:a)
    {
        cin>>e;
    }
    a[n]=0;
    int count=0;
    int i=0;
    while(i<n)
    {
        if(a[i]<a[i+1])
     {
        while(a[i]<a[i+1]&&i<n)
        {
            i++;
        }
        count++;
        i++;
     }
       if(a[i]==a[i+1])
       {
           i++;
       }
        if(a[i]>a[i+1])
        {
       while(a[i]>a[i+1]&&i<n)
     {
            i++;
        }
        count++;
        i++;
     }
    }
    cout<<count;
}

个人总结

从这道题可以抽象出来一个模型：在一个数组中截取一段连续的性质相同的序列，可以采用whie--if--while模型。

while(A)
{
   if(B)
   {
      while(A&&B)
      {
        ++i;
      }
   }
   if(C)
   {
      while(A&&C)
      {
        ++i;
      }
   }
   //.......
}

该模型的意思是，找到同时满足A和B的序列，其中A为i前进条件，B为元素所满足的条件。当序列中下一个元素不满足B的时候，同时退出while与if语句。方便查找满足另一个条件C的序列。