hello啊,今天继续为大家带来算法强化相关的题目,是一道关于排序子序列的题目,让我们一起来消灭它吧!😎😎😎
链接：排序子序列_牛客笔试题_牛客网
来源：牛客网
牛牛定义排序子序列为一个数组中一段连续的子序列,并且这段子序列是非递增或者非递减排序的。牛牛有一个长度为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 3 4 4 5 6
非递减:一组数据总体来说是降序排序,但是中间有相等的数字比如: 7 6 5 4 3 3 2 1
现在来分析题目中的例子
1 2 3 2 2 1
1 2 3是一组,2 2 1是一组
定义一个计数器count
思路:
分为三种情况
1.当i下标的值<i+1下标的值,i往后走,不满足此条件,说明这就是一组,count++,i++,进行下一组
2.当i下标的值=i+1下标的值,i++即可
3.当i下标的值<i+1下标的值,i往后走,不满足此条件,说明这就是一组,count++,i++,进行下一组
注意!!!
但是现在有一个情况,当比较到最后的1,i+1就越界了,没有值和它再比较了,我们可以采用多浪费一个空间的做法,在创建数组的时候长度变成n+1,这样就算最后的1和后面的数字比较,那就是和未初始化的数值比较,(未初始化,默认为0,),这也就是最后一组数据了,因为题目要求数组必须放大于等于1的正整数
看看代码
public class Main { public static void main(String[] args) { //先处理输入 Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int[] array = new int[n + 1]; for (int i = 0; i < n; i++) { array[i] = scanner.nextInt(); } //定义下标 int i = 0; int count = 0; //分三种情况 while (i < n) { if (array[i] < array[i + 1]) { while (i < n && array[i] < array[i + 1]) { i++; } count++; i++; } else if (i < n && array[i] == array[i + 1]) { i++; } else { while (i < n && array[i] > array[i + 1]) { i++; } count++; i++; } System.out.println(count); } } }
真好,又活过一天啊,加油,每天坚持,我们是最棒的
完结散花🌸🌸🌸🌸🌸🌸🌸🌸🌸🌸🌸🌸🌸🌸🌸🌸🌸🌸🌸🌸🌸🌸🌸🌸🌸
