最长数对链的变种：最长交替数对链

题目描述

给定一个数对数组 pairs，其中每个数对 pairs[i] = [a_i, b_i] 满足 a_i < b_i。一个数对链是满足以下条件的一个数对序列：对于序列中任意相邻的两个数对 (x1, y1) 和 (x2, y2)，都有 y1 < x2（即第二个数对的第一个数严格大于第一个数对的第二个数）。

现在定义一种新的链称为“交替链”：在交替链中，相邻数对之间的比较关系必须交替进行。具体来说，如果我们定义关系“小于”为前一个数对的第二个数小于后一个数对的第一个数（即 y1 < x2），关系“大于”为前一个数对的第二个数大于后一个数对的第一个数（即 y1 > x2）。交替链要求从第二个数对开始，它与前一个数对的关系必须与再前一对的关系不同。例如：

• 如果数对2和数对1是“小于”关系，那么数对3和数对2必须是“大于”关系。
• 如果数对2和数对1是“大于”关系，那么数对3和数对2必须是“小于”关系。

第一个数对没有限制。求最长的交替数对链的长度。

示例

输入: pairs = [[1,2], [2,3], [3,4], [4,5], [5,6]]
输出: 2
解释: 最长交替链可以是 [1,2] -> [3,4]（关系：2 < 3），下一个数对必须满足“大于”关系，但[3,4]之后没有数对满足4 > ? 且能形成链，所以长度为2。或者选择[2,3] -> [4,5]（2 < 4），类似地无法继续。注意这里不能选[1,2] -> [2,3]，因为2 < 2 不满足严格小于。

解题思路

这是一个动态规划问题，但需要处理交替关系。我们可以定义两个状态数组：

• dp_less[i]：表示以第 i 个数对结尾，且最后一个关系是“小于”的最长交替链长度。
• dp_greater[i]：表示以第 i 个数对结尾，且最后一个关系是“大于”的最长交替链长度。

由于第一个数对没有前驱关系，我们可以初始化 dp_less[i] = dp_greater[i] = 1。

对于每个数对 i，我们需要检查所有之前的数对 j (0 ≤ j < i)，并根据 pairs[j][1] 和 pairs[i][0] 的关系来更新状态。

详细步骤

1. 预处理：首先将数对按照第一个元素（a_i）升序排序。这样当我们处理第 i 个数对时，所有可能的前驱数对 j 都满足 pairs[j][0] < pairs[i][0]（因为排序后第一个元素递增）。注意：虽然题目没有要求链中数对顺序与原始顺序一致，但排序后便于我们使用动态规划，因为链要求前一个的第二个数小于后一个的第一个数（对于“小于”关系），排序后能保证我们只考虑可能的前驱。

2. 状态定义：

   • dp_less[i]：以第 i 个数对结尾，且它与前一个数对是“小于”关系（即前一个的第二个数 < 当前第一个数）的最长交替链长度。
   • dp_greater[i]：以第 i 个数对结尾，且它与前一个数对是“大于”关系（即前一个的第二个数 > 当前第一个数）的最长交替链长度。

3. 状态转移：

   • 对于每个 i，初始化 dp_less[i] = dp_greater[i] = 1（单独一个数对可以作为一个链）。
   • 对于每个 j 从 0 到 i-1：
     • 如果 pairs[j][1] < pairs[i][0]，说明数对 j 和 i 可以形成“小于”关系。那么以 i 结尾的“小于”链可以从 j 结尾的“大于”链转移过来（因为需要交替，前一个关系必须是“大于”才能接上“小于”）。所以：
       dp_less[i] = max(dp_less[i], dp_greater[j] + 1)
     • 如果 pairs[j][1] > pairs[i][0]，说明数对 j 和 i 可以形成“大于”关系。那么以 i 结尾的“大于”链可以从 j 结尾的“小于”链转移过来（前一个关系必须是“小于”才能接上“大于”）。所以：
       dp_greater[i] = max(dp_greater[i], dp_less[j] + 1)
     • 注意：当 pairs[j][1] == pairs[i][0] 时，不满足严格小于或大于，无法连接，忽略。

4. 结果：最终答案是所有 dp_less[i] 和 dp_greater[i] 中的最大值。

5. 边界情况：如果数组为空，答案为0。

举例说明

以 pairs = [[1,2], [3,4], [2,3], [5,6]] 为例：

1. 排序后：pairs = [[1,2], [2,3], [3,4], [5,6]]（按第一个元素排序）。
2. 初始化：所有 dp_less = [1,1,1,1], dp_greater = [1,1,1,1]。
3. 动态规划更新：
   • i=0：第一个数对，无更新。
   • i=1（数对[2,3]）：
     • j=0：[1,2] 和 [2,3]：2 < 2？不成立（等于），2 > 2？不成立。所以无更新。
     • 结果：dp_less[1]=1, dp_greater[1]=1
   • i=2（数对[3,4]）：
     • j=0：[1,2] 和 [3,4]：2 < 3 成立，所以 dp_less[2] = max(1, dp_greater[0]+1=2) = 2
     • j=1：[2,3] 和 [3,4]：3 < 3 不成立，3 > 3 不成立。
     • 结果：dp_less[2]=2, dp_greater[2]=1
   • i=3（数对[5,6]）：
     • j=0：[1,2] 和 [5,6]：2 < 5 成立，dp_less[3] = max(1, dp_greater[0]+1=2) = 2
     • j=1：[2,3] 和 [5,6]：3 < 5 成立，dp_less[3] = max(2, dp_greater[1]+1=2) = 2
     • j=2：[3,4] 和 [5,6]：4 < 5 成立，dp_less[3] = max(2, dp_greater[2]+1=2) = 2
     • 同时检查大于关系：对于 j=2, 4 > 5 不成立，其他 j 也无大于关系。
     • 结果：dp_less[3]=2, dp_greater[3]=1
4. 最终最大值是 max(2,1,2,1,2,1) = 2。所以最长交替链长度为2，例如 [1,2] -> [3,4]（小于关系），或 [1,2] -> [5,6]（小于关系）。

算法复杂度

• 时间复杂度：O(n²)，因为对于每个 i，我们遍历了所有 j < i。
• 空间复杂度：O(n)，用于存储两个状态数组。

关键点

• 排序是为了保证当我们考虑前驱 j 时，pairs[j][0] < pairs[i][0] 自然成立，这样我们只需要比较 pairs[j][1] 和 pairs[i][0] 来确定关系。但注意，排序后数对的原始顺序被打乱，但题目中链的定义不要求保持原始顺序，所以是可以的。
• 交替关系通过两个状态数组来维护，确保每次转移时关系类型交替变化。

扩展思考

• 如果要求输出具体的最长交替链，可以额外用两个数组记录前驱索引。
• 如果数对数量很大（例如 n=10^5），O(n²) 会超时，可能需要更高效的方法（例如利用数据结构优化），但这通常超出简单动态规划范围。

这个题目是经典最长数对链的变种，增加了交替关系的约束，通过多状态动态规划可以优雅解决。