题解 | #牛牛的数列#

NC155 牛牛的数列

题目

给你一个数组nums，允许改变一个数为任意正整数，求改变一次之后，最长的严格递增的连续子序列的长度是多少

1. 动态规划

要想使得修改一个数后严格递增，需要这个数前面的一段和后面的一段都是严格递增的，且前面一段的最大数要比后面一段的最小数小

所以我们先求最长递增的连续子序列，可以用动态规划来求。

设left[i]表示以i为结尾的最长递增的连续子序列，则有如下转移关系：

如果nums[i] > nums[i-1], 说明把i-1为结尾的最长子序列连上一个i，即left[i] = left[i-1] + 1
否则，前面的数对left[i]没有意义，left[i] = 1.

同理设right[i]表示以i为开头的最长递增的连续子序列，转移过程跟上面是对称的。

最后遍历i，如果nums[i+1] - nums[i-1] >= 2，因为至少要差一个正整数, 说明i+1开头和i-1结尾的两截递增子序列可以连接起来，我们总能找到一个数填进二者之间。使得修改后仍然为递增序列。

以样例为例，图解说明：

图片说明

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums intvector 
     * @return int
     */
    int maxSubArrayLength(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) return 1;
        vector<int> left(n+5), right(n+5);

        left[0] = 1;
        for (int i = 1; i < n; i++) {
            left[i] = nums[i] > nums[i-1] ? left[i-1] + 1 : 1;
        }

        right[n-1] = 1;
        for (int i = n-2; i >= 0; i--) {
            right[i] = nums[i] < nums[i+1] ? right[i+1] + 1 : 1;
        }

        // 考虑单边的情况
        int res = 0;
        for (int i = 0; i < n - 1; i++) {
            res = max(res, left[i]);
        }

        for (int i = n; i >= 1; i--) {
            if (res < right[i] && (i > 1 || nums[i] >= 2)) {
                res = right[i];
            }
        }

        res++; // 需要计算当前次数

        for (int i = 1; i < n-1; i++) {
            if (nums[i+1] - nums[i-1] >= 2)
                res = max(res, left[i-1] + right[i+1] + 1);
        }
        return res;
    }
};

时间复杂度： $O(n)$ , 都是一轮遍历数组
空间复杂度： $O(n)$ , 定义了两个 $n$ 长的一维数组。

2. 递归

方法一中的动态规划也可以用递归来实现。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums intvector 
     * @return int
     */
    int left(vector<int> &nums, int i) {
        if (i == 0) return 1;
        return nums[i] > nums[i-1] ? left(nums, i-1) + 1 : 1;
    }

    int right(vector<int> &nums, int i) {
        if (i == nums.size() - 1) return 1;
        return nums[i] < nums[i+1] ? right(nums, i+1) + 1 : 1;
    }

    int maxSubArrayLength(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) return 1;

        // 考虑单边的情况
        int res = 0;
        for (int i = 0; i < n - 1; i++) {
            res = max(res, left(nums, i));
        }

        for (int i = n; i >= 1; i--) {
            if (res < right(nums, i) && (i > 1 || nums[i] >= 2)) {
                res = right(nums, i);
            }
        }

        res++; // 需要计算当前次数

        for (int i = 1; i < n-1; i++) {
            if (nums[i+1] - nums[i-1] >= 2)
                res = max(res, left(nums, i-1) + right(nums, i+1) + 1);
        }
        return res;
    }
};

时间复杂度： $O(n^2)$ , 递归深度为 $n$ ，外面套了一层 $n$ 长的循环。
空间复杂度： $O(n)$ , 递归栈深度为 $n$ ，每层的空间为 $O(1)$