博客

学习目标：

目标：熟练运用Java所学知识

学习内容：

本文内容：使用java解决 ：排序子序列

题目描述

牛牛定义排序子序列为一个数组中一段连续的子序列,并且这段子序列是非递增或者非递减排序的。牛牛有一个长度为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. ary[i]=ary[i+1]
   
   这种情况不进行操作，因为相等不属于递增也不属于递减，所以continue，进行下一次遍历
2. ary[i]<ary[i+1]
   
   这种情况属于递增区间，需要嵌套while循环继续向后遍历，直到出现ary[i]>ary[i+1],则该区间结束，count++；
3. ary[i]>ary[i+1]
   
   这种情况属于递减区间，需要嵌套while循环继续向后遍历，直到出现ary[i]<ary[i+1],则该区间结束，count++；

需要注意的是遍历时需要遍历到数组最后一个元素，而不能只遍历到倒数第二个元素，因为只遍历到倒数第二个元素一下情况会出错

1 2 1 2 1 2 1 2 1

正确答案会输出5，但是如果只遍历到倒数第二个元素则只会判断出前4个区间，会将最后一个元素 1 默认归为第四个区间，会输出4

所以我们的解决方案是在创建数组时初始大小创建为n+1，也就是比实际数组元素多一，这样我们就可以遍历到最后一个元素且保证ary[i+1]不会越界

实现代码

public class MinDivided {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int length = sc.nextInt();
        int[] ary = new int[length + 1];//创建初始大小比实际元素个数多1
        int index = 0;
        while (sc.hasNext()) {
            ary[index++] = sc.nextInt();
        }
        int res = minDivide(ary, length);
        System.out.println(res);
    }


    public static int minDivide(int[] ary, int length) {
        int count = 0;//记录区间个数
        int cur = 0;//用于遍历的下标
        if (length <= 2) {
            return 1;
        }
        for (; cur < length; cur++) {
            if (ary[cur + 1] == ary[cur]) {
                //情况一：ary[i]=ary[i+1]
                continue;
            } else if (ary[cur] < ary[cur + 1]) {
                //情况二：ary[i]<ary[i+1]
                while (cur < length && ary[cur] <= ary[cur + 1]) {
                    //while循环直到ary[cur]>ary[cur+1]
                    cur++;
                }
                count++;
            } else if (ary[cur] > ary[cur + 1]) {
                //情况三：ary[i]>ary[i+1]
                while (cur < length && ary[cur] >= ary[cur + 1]) {
                    //while循环直到ary[cur]<ary[cur+1]
                    cur++;
                }
                count++;
            }

        }
        return count;
    }
}