修改数组后最大化数组中的连续元素数目

You are given a 0-indexed array nums consisting of positive integers.

Initially, you can increase the value of any element in the array by at most 1.

After that, you need to select one or more elements from the final array such that those elements are consecutive when sorted in increasing order. For example, the elements [3, 4, 5] are consecutive while [3, 4, 6] and [1, 1, 2, 3] are not.

Return the maximum number of elements that you can select.

 

Example 1:

Input: nums = [2,1,5,1,1]
Output: 3
Explanation: We can increase the elements at indices 0 and 3. The resulting array is nums = [3,1,5,2,1].
We select the elements [3,1,5,2,1] and we sort them to obtain [1,2,3], which are consecutive.
It can be shown that we cannot select more than 3 consecutive elements.

Example 2:

Input: nums = [1,4,7,10]
Output: 1
Explanation: The maximum consecutive elements that we can select is 1.

 

Constraints:

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 106

/*
 * 思路：
 * 1. 使用流处理遍历数组并计算每个元素增加1后的频率。
 * 2. 对所有可能的元素进行计数，并使用滑动窗口来找到最大连续元素的数量。
 */
import java.util.Map;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Solution {
    public int maxContinuousElements(int[] nums) {
        Map<Integer, Long> frequencyMap = IntStream.concat(IntStream.of(nums), IntStream.of(nums).map(num -> num + 1))
                .boxed()
                .collect(Collectors.groupingBy(num -> num, Collectors.counting()));
        int maxCount = 0;
        int currentCount = 0;
        for (int key : frequencyMap.keySet()) {
            if (frequencyMap.containsKey(key - 1)) {
                currentCount += frequencyMap.get(key);
            } else {
                currentCount = frequencyMap.get(key).intValue();
            }
            maxCount = Math.max(maxCount, currentCount);
        }
        return maxCount;
    }
}

此题解使用排序加动态规划的方法来解决问题。首先将数组排序，然后使用两个变量 highLength 和 lowLength 来跟踪可以构成的连续子序列的最大长度。highLength 记录不需要增加的连续子序列的长度，而 lowLength 则考虑可以通过增加 1 的方式延伸的子序列的长度。通过迭代排序后的数组，根据当前数与前一个数的关系更新 highLength 和 lowLength，并在每步中更新最大长度 ans。当当前数等于前一个数加一时，这两个长度都增加。如果当前数等于前一个数加二，说明可以通过增加 1 形成新的序列，此时更新 highLength。如果两者差距超过 2，重置这两个长度。这种方法通过一次遍历就能找到可能的最大连续子序列长度。

O(n log n)

O(n)