菜单
文章 Leetcode

3350. 检测相邻递增子数组 II

beautifulremi

beautifulremi

• 阅读本文需 9 分钟

给你一个由 n 个整数组成的数组 nums ，请你找出 k 的 最大值，使得存在 两个 相邻 且长度为 k 的 严格递增

。具体来说，需要检查是否存在从下标 a 和 b (a < b) 开始的 两个 子数组，并满足下述全部条件：

  • 这两个子数组 nums[a..a + k - 1] 和 nums[b..b + k - 1] 都是 严格递增 的。
  • 这两个子数组必须是 相邻的，即 b = a + k。

返回 k 的 最大可能 值。

子数组 是数组中的一个连续 非空 的元素序列。

示例 1：

输入：nums = [2,5,7,8,9,2,3,4,3,1]

输出：3

解释：

  • 从下标 2 开始的子数组是 [7, 8, 9]，它是严格递增的。
  • 从下标 5 开始的子数组是 [2, 3, 4]，它也是严格递增的。
  • 这两个子数组是相邻的，因此 3 是满足题目条件的 最大 k 值。

示例 2：

输入：nums = [1,2,3,4,4,4,4,5,6,7]

输出：2

解释：

  • 从下标 0 开始的子数组是 [1, 2]，它是严格递增的。
  • 从下标 2 开始的子数组是 [3, 4]，它也是严格递增的。
  • 这两个子数组是相邻的，因此 2 是满足题目条件的 最大 k 值。

提示：

  • 2 <= nums.length <= 2 * 10^5
  • -109 <= nums[i] <= 10^9

解题思路

这种思路是一种非常经典且通用的解法，适用于很多“求解满足条件的最大/最小值”的问题。

核心思想

问题的答案 k 具有单调性：

  • 如果一个长度为 k 的解是可行的，那么任何一个比 k 小的长度 k'（例如 k-1）也一定是可行的。
  • 如果一个长度为 k 的解是不可行的，那么任何一个比 k 大的长度 k' 也一定不可行。

这种“要么全行，要么全不行”的特性是使用二分搜索的完美信号。我们可以在所有可能的 k 值（从 0 到 N/2）中进行二分搜索，来快速定位那个“可行”与“不可行”的临界点，这个临界点就是答案。

为了让二分搜索能够进行，我们需要一个高效的 check(k) 函数，它能告诉我们：“长度为 k 的解是否存在？”

实现步骤

1. 预处理 (动态规划) check(k) 函数的核心是快速判断一个子数组 nums[a...b] 是否严格递增。如果每次都去遍历一遍，效率太低。我们可以用动态规划先预计算一个辅助数组，通常命名为 lengths 或 help。

  • lengths[i] 的含义：以 nums[i] 这个元素结尾的严格递增子数组的最大长度是多少。
  • 计算方法：
    • 如果 nums[i] > nums[i-1]，说明递增趋势在延续，所以 lengths[i] = lengths[i-1] + 1。
    • 如果 nums[i] <= nums[i-1]，说明递增中断了，一个新的递增序列从 nums[i] 开始，所以 lengths[i] = 1。
  • 这个预处理过程只需要遍历一次数组，时间复杂度为 O(N)。

2. 二分搜索 (Binary Search) 有了 lengths 数组，check(k) 函数就变得非常高效。我们要找的是否存在两个相邻的长度为 k 的递增子数组，即 nums[a...a+k-1] 和 nums[a+k...a+2k-1]。

  • 第一个子数组 nums[a...a+k-1] 是严格递增的，当且仅当以其结尾元素 nums[a+k-1] 为终点的递增长度大于等于 k。用辅助数组来说，就是 lengths[a+k-1] >= k。
  • 同理，第二个子数组 nums[a+k...a+2k-1] 严格递增，当且仅当 lengths[a+2k-1] >= k。

于是，check(k) 函数的逻辑就变成了：遍历所有可能的结束点 i = a+k-1，检查 lengths[i] >= k 并且 lengths[i+k] >= k 是否成立。

总结

  • 时间复杂度: $O(NlogN)$。$O(N)$ 用于动态规划预处理，之后二分搜索需要进行 $O(logN)$ 轮，每一轮的 check(k) 函数需要 $O(N)$ 的时间。
  • 空间复杂度: $O(N)$，用于存储 lengths 数组。
  • 优点: 思路清晰，是一种标准的解题范式，容易想到，且稳健不易出错。
  • 缺点: 不是最优解，时间复杂度略高。

思路二：一次遍历分块法 (One-Pass Block Traversal)

核心思想

这个算法不再孤立地看每个数字，而是将整个数组看作是由多个连续的、最长的严格递增子数组块拼接而成的。

例如，数组 [2, 5, 7, 8, 9, 2, 3, 4, 3, 1] 被看成是 4 个块：

  • 块1: [2, 5, 7, 8, 9] (长度 5)
  • 块2: [2, 3, 4] (长度 3)
  • 块3: [3] (长度 1)
  • 块4: [1] (长度 1)

最终的答案，只可能在两种情况下产生：

情况一：答案完全位于单个递增块内部 一个足够长的递增块自身就可以被拆分成两个相邻的递增子数组。例如，长度为 L=6 的块 [1,2,3,4,5,6] 可以拆成 [1,2,3] 和 [4,5,6]，此时 k = L / 2 = 3。

情况二：答案跨越两个相邻递增块的边界 答案由前一个块的末尾部分和后一个块的开头部分共同组成。例如，前一个块是 [..., 7, 8, 9] (长度 L1=5)，后一个块是 [2, 3, 4] (长度 L2=3)。

  • 要构成解，我们需要从前一个块的末尾取 k 个元素，并从后一个块的开头取 k 个元素。
  • 这要求 k 不能超过前一个块的长度 L1，也不能超过后一个块的长度 L2。
  • 因此，这种情况下 k 的最大值就是 min(L1, L2)。

实现步骤

我们只需要遍历一次数组，识别出这些连续的递增块，并在每两个块之间以及每个块内部进行检查。

  1. 用一个循环来识别块。循环的每次迭代都处理一个完整的递增块。
  2. 在循环中，用一个变量 prevBlockLength 记录上一个块的长度，用 currentBlockLength 计算当前块的长度。
  3. 对于每一个新识别出的块：
    • 根据情况一更新答案：maxK = max(maxK, currentBlockLength / 2)。
    • 根据情况二更新答案：maxK = max(maxK, min(prevBlockLength, currentBlockLength))。
  4. 遍历结束后，maxK 就是最终答案。

总结

  • 时间复杂度: $O(N)$。因为我们只完整地遍历了数组一次。
  • 空间复杂度: $O(1)$。我们只需要几个变量来存储块的长度。
  • 优点: 时间和空间复杂度都是最优的，代码简洁高效。
  • 缺点: 思路非常巧妙，需要在解题时有灵光一现的洞察力，不如第一种方法直观。

具体代码

解法一

func maxIncreasingSubarrays(nums []int) int {
	n := len(nums)
	if n < 2 {
		return 0
	}

	// --- 1. 动态规划预处理 ---
	// lengths[i] 表示以 nums[i] 结尾的严格递增子数组的最大长度
	lengths := make([]int, n)
	lengths[0] = 1
	maxSingleLength := 1 // 记录单个递增子数组的最大长度，用于优化二分上界
	for i := 1; i < n; i++ {
		if nums[i] > nums[i-1] {
			lengths[i] = lengths[i-1] + 1
		} else {
			lengths[i] = 1
		}
		if lengths[i] > maxSingleLength {
			maxSingleLength = lengths[i]
		}
	}

	// --- 2. 二分搜索寻找最大 k ---
	ans := 0
	left := 1
	// 优化二分上界：k 不可能超过数组长度一半，也不可能超过最长的单个递增子数组长度
	right := min(n/2, maxSingleLength)

	for left <= right {
		// k 是我们当前要验证的子数组长度
		k := left + (right-left)/2

		// check(k): 检查是否存在满足条件的长度为 k 的两个相邻子数组
		found := false
		// i 是第一个子数组的结束下标
		for i := k - 1; i < n-k; i++ {
			// 如果以 i 结尾的递增长度本身就小于 k，
			// 它不可能构成一个长度为 k 的子数组，直接跳过。
			if lengths[i] < k {
				continue
			}

			// 如果第一个子数组满足条件 (lengths[i] >= k)，
			// 再检查相邻的第二个子数组是否也满足条件。
			// 第二个子数组的结束下标为 i+k。
			if lengths[i+k] >= k {
				found = true
				break // 找到一组即可，说明 k 可行
			}
		}

		if found {
			// 如果 k 可行，我们记录下来，并尝试寻找更大的 k
			ans = k
			left = k + 1
		} else {
			// 如果 k 不可行，我们需要缩小 k 的范围
			right = k - 1
		}
	}

	return ans
}

解法二

func maxIncreasingSubarrays(nums []int) int {
	n := len(nums)

	maxK := 0            // 用于存储和更新最终答案 k 的最大值。
	prevBlockLength := 0 // 存储上一个处理过的递增块的长度。

	i := 0
	// 主循环一次遍历数组。通过 i = j 的方式，每次处理一个完整的递增块。
	for i < n {
		// --- 步骤 1: 找到当前递增块的终点，并计算其长度 ---
		j := i + 1
		for j < n && nums[j] > nums[j-1] {
			j++
		}
		currentBlockLength := j - i

		// --- 步骤 2: 根据两种情况更新 maxK ---

		// 情况一：解完全存在于【单个】递增块内部。
		// 一个长度为 L 的块，最多可以支持 k = L / 2。
		maxK = max(maxK, currentBlockLength/2)

		// 情况二：解跨越【两个相邻】的递增块。
		// 这由前一个块的末尾和当前块的开头组成。
		// 只有在不是第一个块时，才能进行此项检查。
		if i > 0 {
			maxK = max(maxK, min(prevBlockLength, currentBlockLength))
		}

		// --- 步骤 3: 更新状态，为下一个块做准备 ---
		prevBlockLength = currentBlockLength
		i = j // 直接跳到下一个块的起始位置。
	}

	return maxK
}
分享