题解 | #牛牛的数列#

打开题解看了看,基本都是在dp,其实这道题给我的第一直觉就是双指针解法.

也就是说,数组可以拆分成一定数量的子数组,这些子数组的长度至少为1且子数组内的元素都是绝对升序排列的,那么题意就转化成求满足条件的相邻子数组的最大长度和,这个条件就:是否能通过改变相邻子数组交界处的一个数,从而将它们连接成一个绝对升序排列的序列. 这里需要注意的有两点.

1.数组已经绝对升序排列,那么返回数组的长度即可.

2.相邻子数组满足连接条件时,此时序列的长度为相邻子数组的长度和;相邻子数组不满足连接条件时,此时也存在一个绝对升序排列的序列,它的长度是较长子数组的长度+1.

那么很明显双指针(或者说是快慢指针)很适合这道题,只需要遍历一遍数组即可.代码如下:

import java.io.IOException;
import java.io.InputStreamReader;

public class Main{
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n =Integer.parseInt(br.readLine().split(" ")[0]);
        int[] nums = new int[n];
        String[] strNums = br.readLine().split(" ");
        for(int i = 0; i < strNums.length; ++i){
            nums[i] = Integer.parseInt(strNums[i]);
        }
        System.out.println(nums.length < 3 ? nums.length : new Main().deal(nums));
        
    }
    private int deal(int[] nums){
        int begin = 0, end = 0, preLength = 0, maxLength = 0;
        while(end < nums.length){
            if((end < nums.length - 1 && nums[end + 1] <= nums[end]) || (end == nums.length - 1)){
                if(judge(nums, begin, end, preLength)){
                    maxLength = Math.max(end - begin + 1 + preLength, maxLength);
                }else{
                    maxLength = Math.max(Math.max(preLength, end - begin + 1) + 1, maxLength);
                }
                preLength = end - begin + 1;
                begin = end + 1; 
            }
            ++ end;
        }
        return maxLength;
    }
    private boolean judge(int[] nums, int begin, int end, int preLength){
        if(begin == 0 || preLength == 1 || begin == end)
            return true;
        if(nums[begin] - nums[begin - 2] > 1 || nums[begin + 1] - nums[begin - 1] > 1)
            return true;
        return false;
    }
}