Medium

题目描述

给定一个由 n 个整数组成的数组 nums，你的任务是找到 k 的最大值，使得存在两个相邻的长度为 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
  • -10^9 <= nums[i] <= 10^9

解题思路

这道题要求找到最大的 k，使得存在两个相邻的长度为 k 的严格递增子数组。

核心思路：

  1. 预处理递增长度：首先遍历数组，计算从每个位置开始的最长递增子数组长度。
  2. 二分搜索优化：由于答案具有单调性（如果 k 可行，那么比 k 小的值也可行），可以使用二分搜索。
  3. 验证可行性：对于给定的 k，检查是否存在位置 i，使得从 i 开始和从 i+k 开始都有长度至少为 k 的递增子数组。

算法步骤：

  1. 计算每个位置的最长递增子数组长度
  2. 二分搜索答案范围 [1, n/2]
  3. 对于每个候选 k，检查是否存在满足条件的相邻子数组对

时间复杂度优化：

  • 预处理：O(n)
  • 二分搜索：O(log n)
  • 每次验证：O(n)
  • 总复杂度：O(n log n)

这种方法比暴力枚举所有可能的 k 值更高效，特别是当数组较大时。

代码实现

class Solution {
public:
    int maxIncreasingSubarrays(vector<int>& nums) {
        int n = nums.size();
        vector<int> inc(n, 1);
        
        // 计算从每个位置开始的最长递增子数组长度
        for (int i = n - 2; i >= 0; i--) {
            if (nums[i] < nums[i + 1]) {
                inc[i] = inc[i + 1] + 1;
            }
        }
        
        int left = 1, right = n / 2, result = 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            bool found = false;
            
            // 检查是否存在长度为 mid 的相邻递增子数组对
            for (int i = 0; i + 2 * mid - 1 < n; i++) {
                if (inc[i] >= mid && inc[i + mid] >= mid) {
                    found = true;
                    break;
                }
            }
            
            if (found) {
                result = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return result;
    }
};

class Solution:
    def maxIncreasingSubarrays(self, nums: List[int]) -> int:
        n = len(nums)
        inc = [1] * n
        
        # 计算从每个位置开始的最长递增子数组长度
        for i in range(n - 2, -1, -1):
            if nums[i] < nums[i + 1]:
                inc[i] = inc[i + 1] + 1
        
        left, right, result = 1, n // 2, 1
        
        while left <= right:
            mid = (left + right) // 2
            found = False
            
            # 检查是否存在长度为 mid 的相邻递增子数组对
            for i in range(n - 2 * mid + 1):
                if inc[i] >= mid and inc[i + mid] >= mid:
                    found = True
                    break
            
            if found:
                result = mid
                left = mid + 1
            else:
                right = mid - 1
        
        return result

public class Solution {
    public int MaxIncreasingSubarrays(IList<int> nums) {
        int n = nums.Count;
        int[] inc = new int[n];
        Array.Fill(inc, 1);
        
        // 计算从每个位置开始的最长递增子数组长度
        for (int i = n - 2; i >= 0; i--) {
            if (nums[i] < nums[i + 1]) {
                inc[i] = inc[i + 1] + 1;
            }
        }
        
        int left = 1, right = n / 2, result = 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            bool found = false;
            
            // 检查是否存在长度为 mid 的相邻递增子数组对
            for (int i = 0; i + 2 * mid - 1 < n; i++) {
                if (inc[i] >= mid && inc[i + mid] >= mid) {
                    found = true;
                    break;
                }
            }
            
            if (found) {
                result = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return result;
    }
}

var maxIncreasingSubarrays = function(nums) {
    const n = nums.length;
    const inc = new Array(n).fill(1);
    
    // 计算从每个位置开始的最长递增子数组长度
    for (let i = n - 2; i >= 0; i--) {
        if (nums[i] < nums[i + 1]) {
            inc[i] = inc[i + 1] + 1;
        }
    }
    
    let left = 1, right = Math.floor(n / 2), result = 1;
    
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        let found = false;
        
        // 检查是否存在长度为 mid 的相邻递增子数组对
        for (let i = 0; i + 2 * mid - 1 < n; i++) {
            if (inc[i] >= mid && inc[i + mid] >= mid) {
                found = true;
                break;
            }
        }
        
        if (found) {
            result = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n log n)
空间复杂度O(n)