如何提取满足元素递增条件的最长连续数对序列？

问题说明 #

• 核心要求：从数对列表中提取最长序列，序列中后续数对的第一个元素必须大于当前数对的第一个元素，且第二个元素也大于当前数对的第二个元素
• 示例：给定数对[(3, 9), (4, 6), (5, 7), (6, 0), (8, 10)]，满足要求的最长序列为[(4, 6), (5, 7), (8, 10)]

解决方案 #

这个问题本质是二维最长递增子序列的变种，可通过以下高效步骤解决：

步骤1：对数对列表排序 #

先按数对的第一个元素升序排列；若第一个元素相同，则按第二个元素降序排列。这一步确保第一个元素已满足递增要求，同时避免同一第一个元素的数对被重复选入序列。

步骤2：提取第二个元素序列，求最长递增子序列（LIS） #

由于第一步已保证第一个元素递增，只需对第二个元素求LIS，对应的数对序列就是满足条件的最长序列。为了还原具体序列，需要记录每个元素的前驱索引，最后回溯得到完整序列。

代码实现 #

from bisect import bisect_left

def longest_valid_pair_sequence(pairs):
    # 排序规则：按第一个元素升序，第一个元素相同时按第二个元素降序
    sorted_pairs = sorted(pairs, key=lambda x: (x[0], -x[1]))
    if not sorted_pairs:
        return []
    
    tails = []          # 存储当前最长子序列末尾的第二个元素值
    tails_indices = []  # 存储tails中对应元素在sorted_pairs中的索引
    prev_indices = [-1] * len(sorted_pairs)  # 记录每个元素的前驱索引
    
    for idx, (a, b) in enumerate(sorted_pairs):
        # 用二分查找确定当前元素在tails中的位置
        pos = bisect_left(tails, b)
        if pos == len(tails):
            tails.append(b)
            tails_indices.append(idx)
        else:
            tails[pos] = b
            tails_indices[pos] = idx
        # 记录前驱元素的索引
        if pos > 0:
            prev_indices[idx] = tails_indices[pos - 1]
    
    # 回溯构建结果序列
    current_idx = tails_indices[-1]
    result = []
    while current_idx != -1:
        result.append(sorted_pairs[current_idx])
        current_idx = prev_indices[current_idx]
    
    # 反转得到正序序列
    return result[::-1]

# 测试示例
test_pairs = [(3, 9), (4, 6), (5, 7), (6, 0), (8, 10)]
print(longest_valid_pair_sequence(test_pairs))
# 输出：[(4, 6), (5, 7), (8, 10)]

复杂度说明 #

• 排序阶段：O(n log n)
• LIS求解阶段：O(n log n)
• 整体时间复杂度：O(n log n)，比传统动态规划的O(n²)效率更高，适合处理大规模数对列表。

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