数组k长度非连续子序列的最大元素最小值求解优化方案咨询

问题明确 #

给定数组arr和整数k，需要找出所有长度为k、元素不相邻的子序列，计算每个子序列的最大值后，求这些最大值中的最小值。比如示例中arr = [2, 3, 5, 9]，k=2，最终结果为5。

暴力枚举的局限性很明显：当数组长度较大时，子序列数量呈指数级增长，时间复杂度完全不可接受，必须用更高效的方法优化。

最优解法：二分查找+贪心验证 #

这是效率最高的解法，时间复杂度为O(n log M)（n是数组长度，M是数组元素的最大值），适合处理大规模数据。

核心思路 #

我们要找的是最小的最大值，可以转化为：找到最小的target，使得数组中存在至少k个不相邻的元素都≤target。通过二分查找缩小target的范围，再用贪心算法验证当前target是否满足条件。

具体步骤 #

1. 二分查找范围初始化：左边界left为数组最小值，右边界right为数组最大值。
2. 二分查找循环：
   • 计算中间值mid = (left + right) // 2
   • 用贪心算法验证：遍历数组，尽可能多地选取≤mid且不相邻的元素，统计选取数量
   • 如果选取数量≥k：说明mid是可行解，尝试找更小的target，将right = mid
   • 如果选取数量<k：说明mid太小，需要增大target，将left = mid + 1
3. 终止条件：当left == right时，这个值就是答案。

示例验证（arr=[2,3,5,9], k=2） #

• 初始left=2，right=9，mid=5：遍历数组，选2（≤5）→跳过3；选5（≤5）→跳过9，共选2个，满足k=2，将right=5
• 接下来left=2，right=5，mid=3：选2（≤3）→跳过3；5>3、9>3，共选1个，不满足，将left=4
• 然后left=4，right=5，mid=4：选2（≤4）→跳过3；5>4、9>4，共选1个，不满足，将left=5
• 此时left=right=5，即为答案。

代码实现（Python） #

def find_min_max(arr, k):
    left = min(arr)
    right = max(arr)
    
    def is_possible(target):
        count = 0
        i = 0
        n = len(arr)
        while i < n:
            if arr[i] <= target:
                count += 1
                i += 2  # 选当前元素，跳过下一个
            else:
                i += 1
            if count >= k:
                return True
        return count >= k
    
    while left < right:
        mid = (left + right) // 2
        if is_possible(mid):
            right = mid
        else:
            left = mid + 1
    return left

# 测试示例
arr = [2, 3, 5, 9]
k = 2
print(find_min_max(arr, k))  # 输出5

备选解法：动态规划 #

如果数组规模较小，可以用动态规划实现，时间复杂度为O(nk)。

核心思路 #

定义dp[i][j]表示前i个元素中选j个非相邻元素时，这些子序列的最大值的最小值。

状态转移 #

• 不选第i个元素：dp[i][j] = dp[i-1][j]
• 选第i个元素：dp[i][j] = max(arr[i-1], dp[i-2][j-1])（注意数组索引从0开始）
• 最终dp[i][j]取两种情况的最小值。

代码实现（Python） #

def find_min_max_dp(arr, k):
    n = len(arr)
    # 初始化dp数组，dp[i][j]表示前i个元素选j个的最小最大值
    dp = [[float('inf')] * (k+1) for _ in range(n+1)]
    # 选0个元素时，没有最大值，设为-inf（不影响后续max计算）
    for i in range(n+1):
        dp[i][0] = float('-inf')
    
    for i in range(1, n+1):
        for j in range(1, k+1):
            # 不选第i个元素
            dp[i][j] = dp[i-1][j]
            # 选第i个元素，需要前i-2个元素选j-1个
            if i >= 2:
                current = max(arr[i-1], dp[i-2][j-1])
                dp[i][j] = min(dp[i][j], current)
            # 当i=1时，只能选第1个元素（j=1）
            elif j == 1:
                dp[i][j] = min(dp[i][j], arr[i-1])
    return dp[n][k]

# 测试示例
arr = [2, 3, 5, 9]
k = 2
print(find_min_max_dp(arr, k))  # 输出5

总结 #

• 当数组规模较大时，二分查找+贪心验证是最优选择，效率远高于暴力枚举和动态规划。
• 动态规划适合小规模场景，逻辑直观但时间复杂度较高。

内容的提问来源于stack exchange，提问作者bloomsdayforever