统计列表中指定长度k的递增趋势子集数量

问题定义 #

给定一个数值列表和正整数k，统计列表中连续且严格递增的k长度子数组（即连续元素组成的子集）的数量。比如输入[1,2,3,4,5,6]、k=3时，结果为4，对应子数组(1,2,3),(2,3,4),(3,4,5),(4,5,6)。

核心思路 #

1. 边界情况优先处理：
   • 如果k大于列表长度，直接返回0（不可能存在符合要求的子集）
   • 如果k=1，每个元素自身都是符合要求的子集，返回列表长度即可
2. 遍历统计连续递增段：
   • 遍历列表，追踪当前连续递增段的长度
   • 每当遇到不满足递增的元素时，计算当前递增段能贡献的k长子集数量（仅当段长≥k时，贡献值为段长 - k + 1），然后重置当前段长度
   • 遍历结束后，别忘了处理最后一个递增段

代码实现（Python） #

def count_increasing_k_subarrays(arr, k):
    arr_len = len(arr)
    # 边界情况
    if k > arr_len or not arr:
        return 0
    if k == 1:
        return arr_len
    
    total = 0
    current_streak = 1
    
    for i in range(1, arr_len):
        if arr[i] > arr[i-1]:
            current_streak += 1
        else:
            if current_streak >= k:
                total += current_streak - k + 1
            current_streak = 1
    # 处理最后一段递增序列
    if current_streak >= k:
        total += current_streak - k + 1
    return total

# 测试示例
test_arr = [1,2,3,4,5,6]
test_k = 3
print(count_increasing_k_subarrays(test_arr, test_k))  # 输出4

额外测试案例 #

比如输入列表[1,3,2,4,5,7,6]、k=2：

• 连续递增段为[1,3]（长度2）、[2,4,5,7]（长度4）、[6]（长度1）
• 贡献值分别为2-2+1=1和4-2+1=3，总计4个符合要求的子数组：(1,3),(2,4),(4,5),(5,7)

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