求解排列中满足子排列条件的连续区间总数

问题定义 #

n阶排列是由1到n每个整数恰好出现一次的序列。例如[3,1,2]、[1]、[1,2,3,4]是排列，而[2]、[4,1,2]、[3,1]不是。

输入包含两部分：

• 排列的元素个数n
• 长度为n的排列本身

要求统计有多少个区间[l;r]（1≤l≤r≤n），使得子序列p[l..r]也是一个排列。

示例 #

输入：7；[6,3,4,1,2,7,5]
答案：4
对应的子排列：

• [6,3,4,1,2,7,5]（整个序列）
• [1]（单个元素）
• [1,2]（长度为2的子序列）
• [3,4,1,2]（长度为4的子序列）

用户现有代码 #

用户仅处理了整个序列和单个元素1的情况，代码如下：

numbers = int(input("Amount of elements in permutation: "))
perm = list(input("Permutation: "))
perm = [ int(x) for x in perm if x != " "]
amount = 1
first = 1
if len(perm) == numbers and int(max(perm)) == numbers and int(min(perm)) == 1:
    if first in perm and len(perm) > 1:
        amount += 1

完整解法思路与代码 #

核心思路 #

一个子序列p[l..r]是排列的充要条件：

• 子序列的最大值减去最小值等于区间长度减1（即max - min = r - l）
• 子序列中所有元素不重复（因原序列是排列，满足第一个条件时自动满足此条）

基于此，我们可以遍历所有可能的区间，实时维护区间的最大值和最小值，检查是否符合条件即可。

完整代码 #

n = int(input("输入排列的元素个数n: "))
# 处理空格分隔的排列输入
perm = list(map(int, input("输入排列（元素用空格分隔）: ").split()))

count = 0

# 遍历所有左端点（0-based索引）
for i in range(n):
    current_max = perm[i]
    current_min = perm[i]
    # 遍历所有右端点 >= 左端点
    for j in range(i, n):
        current_max = max(current_max, perm[j])
        current_min = min(current_min, perm[j])
        # 检查核心条件：max - min = 区间长度-1（索引差j-i对应长度差）
        if current_max - current_min == j - i:
            count += 1

print(f"符合条件的子排列区间数量: {count}")

代码说明 #

1. 输入优化：改用split()处理空格分隔的排列，避免原代码中字符列表解析的问题
2. 双层循环：外层控制左端点，内层扩展右端点，覆盖所有可能的区间
3. 实时维护：每次扩展右端点时更新当前区间的最大值和最小值
4. 条件判断：通过current_max - current_min == j - i直接验证子序列是否为排列
5. 复杂度：O(n²)，适用于n≤1000的场景；若需处理更大n，可通过单调栈优化至O(n)

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