每日OJ_牛客_排序子序列

目录

牛客_排序子序列

题解及代码

牛客_排序子序列

排序子序列_牛客笔试题_牛客网

题解及代码

本题依次比较整个数组

1. v[i+1]>v[i] ，则进入非递减序列判断，直到遍历到下一个值不大于等于为止count++，然后进行下一位置的判断
2. v[i+1]<v[i]，则进入非递增序列判断，直到遍历到下一个值不小于等于为止count++，然后进行下一位置的判断
3. v[i+1] == v[i]不进行操作，++i进行下一位置遍历，因为相等既可以属于非递增序列，也可以属于非递减 序列。
4. 本题注意点：本题开始比较v[i+1]与a[i]进行比较，为了避免越界，数组定义为n+1个，同时给v[n] = 0;

#include <iostream>
#include <vector>
using namespace std;
int main()
{
	int n = 0, cnt = 0;
	cin >> n;
	vector<int> v(n + 1, 0); // 防止数组越界
	for (int i = 0; i < n; ++i)
	{
		cin >> v[i];
	}
	for (int i = 0; i < n; ++i)
	{
		if (v[i+1] > v[i]) // 非递减
        {
            while(i < n && v[i + 1] >= v[i])
            {
                ++i; // i走到非递减尽头
            }
            ++cnt;
        }
		else if (v[i + 1] < v[i]) // 非递增
        {
            while(i < n && v[i + 1] <= v[i])
            {
                ++i; // i走到非递增尽头
            }
            cnt++;
        }
	}
	cout << cnt;
	return 0;
}