题目

给你一个由 n 个整数组成的数组 nums 和一个整数 k，请你确定是否存在 两个 相邻 且长度为 k 的 严格递增 子数组。具体来说，需要检查是否存在从下标 a 和 b (a < b) 开始的 两个 子数组，并满足下述全部条件：

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

如果可以找到这样的 两个 子数组，请返回 true；否则返回 false。

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

示例 1：

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

输出：true

解释：

• 从下标 2 开始的子数组为 [7, 8, 9]，它是严格递增的。
• 从下标 5 开始的子数组为 [2, 3, 4]，它也是严格递增的。
• 两个子数组是相邻的，因此结果为 true。

示例 2：

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

输出：false

提示：

• 2 <= nums.length <= 100
• 1 <= 2 * k <= nums.length
• -1000 <= nums[i] <= 1000

解题思路

暴力法

算法的核心是：遍历数组中每一个可能成为“第一段”递增子数组的起始位置。对于每一个这样的起始位置，都去检查它和紧邻它的后一个子数组是否都满足“严格递增”的条件。只要找到任何一对满足条件的，就立刻返回 true。如果遍历完所有可能性都找不到，就说明不存在，最后返回 false。

1. 初步筛选（边界条件检查）
   • if 2 * k > len(nums)
   • 思路: 在开始搜索之前，代码先做了一个有效性判断。如果数组的总长度 len(nums) 甚至都不足以容纳两个长度为 k 的子数组（即总长度小于 2*k），那么满足条件的子数组对就绝不可能存在。这是一个很好的优化，可以提前终止无效的计算。
2. 主循环：遍历所有可能的“相邻子数组对”
   • for i := 0; i <= len(nums) - 2 * k; i++
   • 思路: 这是算法的主体。这里的 i 代表了我们假设的第一个长度为 k 的子数组的起始下标。
   • 这个循环的范围 len(nums) - 2 * k 设置得非常精确。它确保了以 i 开头的两个相邻子数组（总长度为 2*k）不会超出整个数组的边界。这个循环实际上是在整个 nums 数组上移动一个长度为 2*k 的“大窗口”。
3. 第一轮检查：验证第一个子数组
   • pass := true 和随后的 for 循环
   • 思路: 对于外层循环确定的每一个起始点 i，代码首先要验证从 i 到 i + k - 1 的这个子数组是否是严格递增的。
   • 它通过一个内部循环，逐一比较相邻元素 nums[i + j] 和 nums[i + j - 1]。一旦发现 nums[i + j] <= nums[i + j - 1]，就说明这个子数组不满足“严格递增”的条件。此时，pass 标志位被设为 false，并立刻 break 跳出这个内部检查循环，因为没必要再继续检查下去了。
4. 第二轮检查：验证第二个（相邻的）子数组
   • if pass 块内的逻辑
   • 思路: 只有在第一个子数组成功通过检查（pass 仍为 true）后，我们才有必要去检查紧随其后的第二个子数组。
   • 第二个子数组的起始位置 l 自然就是 i + k。
   • 代码使用了与第一轮检查完全相同的逻辑（用 pass2 标志位）来验证从 l 到 l + k - 1 的这个子数组是否也满足严格递增。
5. 得出结论
   • if pass2 { return true }
   • 思路: 如果第一个子数组通过了检查 (pass 为 true)，并且第二个子数组也通过了检查 (pass2 为 true)，那么我们就找到了题目要求的一对子数组。任务完成，函数立即返回 true，不再进行任何后续的循环和检查。
   • return false
   • 思路: 如果外层的主循环全部执行完毕，都没有触发中间的 return true 语句，那就意味着在所有可能的位置上，都未能找到符合条件的相邻递增子数组对。因此，在循环结束后，函数返回 false。

动态规划法

当前代码的解法时间复杂度是 O(n⋅k)，因为它有一个外层循环（最多遍历 n−2k 次）和两个内层循环（每个循环 k 次）。当 k 比较大时，性能会下降。

一个更好的方法是采用 动态规划 (Dynamic Programming) 的思想，通过一次预处理来避免重复计算，从而将时间复杂度优化到 O(n)。

暴力法的缺点是，对于每一个窗口，都从头开始检查它是否是递增的。例如，当检查 [2,5,7] 和 [5,7,8] 时，5,7 这个递增关系被检查了两次。

我们可以通过一次遍历，记录下以每个位置 i 为结尾的连续递增子数组的长度。有了这个信息，我们就能在 O(1) 的时间内判断任何一个子数组是否是严格递增的。

• 创建预处理数组： 创建一个与 nums 等长的数组，我们称之为 increasing_len。increasing_len[i] 用来存储以 nums[i] 这个元素结尾的严格递增子数组的最大长度。
• 填充预处理数组： 我们只需要遍历一次 nums 数组就可以填充好 increasing_len。
  • increasing_len[0] 永远是 1，因为单个元素自成一个长度为1的递增序列。
  • 从 i = 1 开始遍历 nums：
    • 如果 nums[i] > nums[i-1]，说明递增序列可以延续，那么 increasing_len[i] = increasing_len[i-1] + 1。
    • 如果 nums[i] <= nums[i-1]，说明递增序列在此处中断了，需要重新开始计数，所以 increasing_len[i] = 1。 这个过程的时间复杂度是 O(n)。
• 最终检查： 有了 increasing_len 数组后，问题就变得简单了。我们要找的是否存在一个起始点 a，使得 nums[a..a+k-1] 和 nums[a+k..a+2k-1] 都严格递增。所以，我们只需要再遍历一次，检查是否存在任何一个 i（这里的 i 对应检查的终点），满足 increasing_len[i] >= k 并且 increasing_len[i-k] >= k。
  • 子数组 nums[a..a+k-1] 严格递增，等价于以 a+k-1 结尾的连续递增序列长度至少为 k，即 increasing_len[a+k-1] >= k。
  • 同理，子数组 nums[a+k..a+2k-1] 严格递增，等价于 increasing_len[a+2k-1] >= k。
• 这个检查的循环可以从 i = 2k - 1 开始，直到数组末尾。
• 如果找到了这样的 i，立即返回 true。
• 如果循环结束都没找到，就返回 false。 这个过程的时间复杂度也是 O(n)。

具体代码

暴力法

func hasIncreasingSubarrays(nums []int, k int) bool {
    // 边界条件：如果数组长度不足以容纳两个长度为 k 的子数组，直接返回 false。
    if 2 * k > len(nums) {
        return false
    }

    // 遍历所有可能的起始位置 i，确保能容纳两个相邻的长度为 k 的子数组。
    // i 是第一个子数组的起始索引。
    for i := 0; i <= len(nums) - 2 * k; i++ {
        // 标志位，用于检查第一个子数组 nums[i..i+k-1] 是否严格递增。
        pass := true
        for j := 1; j < k; j++ {
            // 检查子数组内相邻元素是否满足严格递增。
            if nums[i + j] <= nums[i + j - 1] {
                pass = false // 如果不满足，设置标志位为 false 并跳出内层循环。
                break
            }
        } 

        // 如果第一个子数组是严格递增的，才继续检查第二个子数组。
        if pass {
            // 第二个子数组的起始索引。
            l := i + k
            // 标志位，用于检查第二个子数组 nums[l..l+k-1] 是否严格递增。
            pass2 := true
            for j := 1; j < k; j++ {
                // 同样地，检查第二个子数组内相邻元素。
                if nums[l + j] <= nums[l + j - 1] {
                    pass2 = false // 如果不满足，设置标志位为 false 并跳出。
                    break
                }
            }

            // 如果第二个子数组也是严格递增的，说明找到了符合条件的两个相邻子数组。
            if pass2 {
                return true
            }
        }
    }

    // 如果遍历完所有可能的起始位置都没有找到，则返回 false。
    return false
}

动态规划法

func hasIncreasingSubarrays(nums []int, k int) bool {

    n := len(nums)
    // 边界条件和原先一样
    if 2 * k > n {
        return false
    }

    // 步骤 1 & 2: 创建并填充预处理数组
    // increasingLen[i] 表示以 nums[i] 结尾的严格递增子数组的长度
    increasingLen := make([]int, n)
    increasingLen[0] = 1
    for i := 1; i < n; i++ {
        if nums[i] > nums[i-1] {
            increasingLen[i] = increasingLen[i-1] + 1
        } else {
            increasingLen[i] = 1
        }
    }

    // 步骤 3: 最终检查
    // 我们需要寻找一个点 i，使得它是一个长度为k的递增子数组的结尾，
    // 并且它前面的那个相邻块也是一个长度为k的递增子数组。
    // i-k 就是前一个块的结尾。
    // 循环从 2*k - 1 开始，这是第一个可能满足条件的检查点。
    for i := 2*k - 1; i < n; i++ {
        // 检查以 i 结尾的子数组和以 i-k 结尾的子数组
        if increasingLen[i] >= k && increasingLen[i-k] >= k {
            return true
        }
    }

    // 遍历完所有可能都未找到
    return false
}