每日OJ题_牛客_排序子序列_模拟_C++_Java

目录

牛客_排序子序列_模拟

题目解析

C++代码

Java代码

牛客_排序子序列_模拟

排序子序列_牛客笔试题_牛客网 (nowcoder.com)

描述：

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

题目解析

根据题意用指针模拟即可，直接放代码。

C++代码

#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 = 1; i <= n; ++i) // n是判断最后一个元素单独为一个序列的情况
    {
        if(i == n - 1) // 数组不多开一个空间且 i != n的话就这样写
        {
            ++cnt;
            break;
        }
        if(v[i] > v[i - 1])
        {
            while(i < n && v[i] >= v[i - 1])
            {
                ++i;
            }
            ++cnt;
        }
        else if(v[i] < v[i - 1]) // 注意不能直接写成if
        {
            while(i < n && v[i] <= v[i - 1])
            {
                ++i;
            }
            ++cnt;
        }
        else
        {
            while(i < n && v[i] == v[i - 1])
            {
                ++i;
            }
        }
    }
	cout << cnt;
	return 0;
}

Java代码

import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main
{
    public static void main(String[] args) 
    {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) 
        {
            arr[i] = in.nextInt();
        }
        int ret = 0, i = 0;
        while(i < n)
        {
            if(i == n - 1)
            {
                ret++;
                break;
            }
            if(arr[i] < arr[i + 1])
            {
                while(i + 1 < n && arr[i] <= arr[i + 1]) i++;
                ret++;
            }
            else if(arr[i] > arr[i + 1])
            {
                while(i + 1 < n && arr[i] >= arr[i + 1]) i++;
                ret++;
            }
            else
            {
                while(i + 1 < n && arr[i] == arr[i + 1]) i++;
            }
            i++;
        }
        System.out.println(ret);
    }
}