牛牛的排序子序列问题

短命女 2024-03-31 10:11 32阅读 0赞

### 一.问题描述 ###

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

3）输出描述： 输出一个整数表示牛牛可以将A**至少**划分为多少段排序子序列

4）示例:  
输入 6 1 2 3 2 2 1  
输出 2

### 二.解题思路 ###

1）  
子序列有如下要求： 非递增或非递减排序；  
递增序列： 1 2 3 4 …  
递减序列： 9 7 6 5 …  
既不递增也不递减序列： 1 2 2 3 4 或者 9 7 6 6 6 5

**综上所述：子序列的顺序可以任意排序，是不做要求的**

那么如何判定其为子序列？  
非递增则其为既不递增也不递减或者递减序列；  
非递减则其为既不递增也不递减或者递增序列；

综上所述：  
当给定一组数据， 其原本为递增序列（1 2 3 …）直至下一个数让其改变了原本的递增序列（1 2 3 **2**… 或者 1 2 3 **3** ），则此时这个数之前的所有数可以分为一组，看作递增或者既不递增也不递减的子序列；  
当给定一组数据，其原本为递减序列（6 5 4 …） 直至下一个数让其改变了原本的递减序列（6 5 4 **3**… 或者 6 5 4 **4**）， 则此时这个数之前的所有数可以分为一组，看作递减或者既不递增也不递减的子序列；

2）输出要求： 可以将数组A至少划分为多少段子序列，**至少**是关键！！！  
那么，如何去判断至多至少问题呢？

看一组例子：  
![在这里插入图片描述][6e06b4991813451b92a38f467398abc2.png]a按照上述判定子序列规则， 可以得到如下子序列分组

![在这里插入图片描述][8ac8bd5b07934cb189384ab385b4857c.png]  
1）原本为一个递减序列（6 2 1），下一个1 排进来时，变成 （6 2 1 1）， 符合要求让原本的递减序列变成了一个既不递增也不递减序列，因此 （6 2 1） 可以作为一个子序列  
![在这里插入图片描述][9e4aa6bff44941c9a91736145ad7b5ce.png]  
2）原本为一个暂时无序序列（1），下一个1排进来时，变成了（1 1 ），符合要求让原本的序列变成了一个既不递增也不递减序列，因此（1）可以单独做一个子序列  
![在这里插入图片描述][ffaf328792ee459991a0295173786f3d.png]  
3）原本为一个递增序列（1 2 ）， 下一个1 排进来时，变成了（1 2 1），符合要求让原本递增的序列变成了一个既不递增也不递减序列，因此（1 2 ）可以单独做一个子序列  
![在这里插入图片描述][0df48fbd10a94745bfdc130eebb26c6e.png]  
4）最后的递增序列（1 2），由于数据已经遍历完，但仍未改变其序列，因此，最后的递增序列（1 2） 可以单独做一个子序列

**综上所述： 上述一组数据，一共可以有四个子序列**

但是，上述的一组数据，还可以按照要求如下分  
![在这里插入图片描述][85fd1c5df4b84f7aa66c89e97ffd8fcd.png]  
1）当 6 ， 2， 1 依次排进来时，此时为一个递减序列，但当第二个1排进来时，发现其变成了一个既不递增也不递减序列（6 2 1 1），但当第三个1也排进来时，其任然可以保持为一个既不递增也不递减序列，因此我们可以将其归为一个子序列（6 2 1 1 1）  
![在这里插入图片描述][2213ba246e9f49989e79e1577207674a.png]  
2）此时的三个数据（ 2 1 2） 很明显可以分为两组子序列（2 1） 和 （2），如此分的话，可以认为上述一组数可以有三个子序列，比第一次的划分少一个。

综上所述： 如果需要满足至少这个条件的话，当下一个数和当前数相比，**如果相同时，应当让当前这个数和前面的数归为一组**。 **因此为了保持最少的子序列，子序列的判定就变成了当遇到违背其递增或者递减时即可作为划分条件**

### 三.代码实现（java） ###

public static int fun2() {
        
            Scanner scanner = new Scanner(System.in);
            int n = scanner.nextInt(); // 数组长度
            int[] arr = new int[n + 1]; // 防止遍历数组越界
            int len = 0;
            while (scanner.hasNextInt()) {
        
                // 存储数据
                for (int i = 0; i < n; i++) {
        
                    arr[i] = scanner.nextInt();
                }
                int i = 0;
                len = 0;
                while (i < n) {
        
                    // 递增
                    if (arr[i] < arr[i + 1]) {
        
                        // 向后继续执行 -- 前提为i不越界,且满足升序
                        while (i < n && arr[i] < arr[i + 1]) {
        
                            i++;
                        }
                        // 此时已经非递增 (arr[i+1] <= arr[i]) 则之前为一组
                        len++;
                        // i+1 为下一组子序列开头
                        i++;
                    }
                    // 相等 -- 既不递增也不递减序列 -- 继续向后排序
                    else if (arr[i] == arr[i + 1]) {
        
                        while (i < n && arr[i] == arr[i + 1]) {
        
                            i++;
                        }
                        // 此时 arr[i+1] > arr[i]  或者  arr[i+1] < arr[i] 则当前arr[i]与之前分为一组
                        i++;
                    }
                    // 递减
                    else {
        
                        while (i < n && arr[i] > arr[i + 1]) {
        
                            i++;
                        }
                        len++;
                        i++;
                    }
                }
            }
            return len;
        }

*  *最后，希望各位可以多多指点！*\*

[6e06b4991813451b92a38f467398abc2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/fc9273e60c214161a366d247fc94faab.png
[8ac8bd5b07934cb189384ab385b4857c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/53f79ba4c9e74e15b6198c8b1d48ea9d.png
[9e4aa6bff44941c9a91736145ad7b5ce.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/5a2cbe9de05641938d0e27bae269b7d2.png
[ffaf328792ee459991a0295173786f3d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/9393cc9440ea4ce6b34d5df251504809.png
[0df48fbd10a94745bfdc130eebb26c6e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/5b089cc9e0874b06a48178a41914b9c7.png
[85fd1c5df4b84f7aa66c89e97ffd8fcd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/25386a91a6fb4c03802e99008906045c.png
[2213ba246e9f49989e79e1577207674a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/9f48359808934d348dfd184c6e20510e.png