2025-09-10：删除一个冲突对后最大子数组数目。用go语言，给你一个正整数 n，数组 nums 为按顺序的 1 到 n。还有若干对冲突关系 conflictingPairs，其中每一对 [a, b] 表示数字 a 和 b 互相冲突。现在要求从这些冲突对中删去且仅删去一对（不能不删也不能删多于一对）。删掉后，统计 nums 中所有长度至少为 1 的连续子段中，有多少个子段不包含任意剩余冲突对中的两个数（即对于任一剩余的 [a,b]，该子段不会同时包含 a 和 b）。返回通过恰好删除一个冲突对后能达到的最大这样的子段数量。

2 <= n <= 100000。

1 <= conflictingPairs.length <= 2 * n。

conflictingPairs[i].length == 2。

1 <= conflictingPairs[i][j] <= n。

conflictingPairs[i][0] != conflictingPairs[i][1]。

输入： n = 4, conflictingPairs = [[2,3],[1,4]]。

输出： 9。

解释：

从 conflictingPairs 中删除 [2, 3]。现在，conflictingPairs = [[1, 4]]。

在 nums 中，存在 9 个子数组，其中 [1, 4] 不会一起出现。它们分别是 [1]，[2]，[3]，[4]，[1, 2]，[2, 3]，[3, 4]，[1, 2, 3] 和 [2, 3, 4]。

删除 conflictingPairs 中一个元素后，能够得到的最大子数组数量是 9。

题目来自力扣3480。

分步骤描述过程

1. 问题理解

• 给定一个顺序数组 nums = [1, 2, 3, ..., n] 和若干冲突对 conflictingPairs（每个冲突对 [a, b] 表示 a 和 b 不能同时出现在同一个子段中）。
• 要求恰好删除一个冲突对（即从 conflictingPairs 中移除一对），然后统计所有连续子段（长度至少为1）中，不包含任意剩余冲突对（即子段中不能同时出现任何剩余冲突对的两个数）的数量。
• 目标是找到删除哪一对冲突能使得这样的子段数量最大，并返回该最大数量。

2. 关键观察

• 删除一个冲突对后，剩余冲突对集合为 conflictingPairs 减去被删除的那一对。
• 一个子段是“合法”的当且仅当它不包含任何剩余冲突对中的两个数（即对于剩余每个冲突对 [a, b]，子段不同时包含 a 和 b）。
• 注意：即使删除一对冲突，剩余冲突对可能仍然很多，直接枚举所有子段和所有冲突对会超时（因为 n 最大为100000）。
• 需要高效方法：通常这类问题可以通过预处理冲突关系，并利用双指针/滑动窗口来统计合法子段数（但这里需要枚举删除哪一对冲突）。

3. 代码思路（大致）

• 预处理冲突对：对于每个数字 i，记录与其冲突的最小数字（以及次小数字？），以便快速判断子段是否合法。
  • 具体地，对于每个冲突对 [a, b]（假设 a < b），那么对于数字 a，b 是一个与其冲突的数字（且是大于 a 的）。我们为每个 a 记录最小的两个冲突数字（即最小的 b），因为可能多个冲突对涉及同一个 a。
  • 定义数组 bMin1 和 bMin2：bMin1[i] 表示与 i 冲突的最小数字（大于 i），bMin2[i] 表示与 i 冲突的次小数字（如果存在）。
• 计算不删除任何冲突对时的合法子段数？（但这里需要删除一对，所以实际上需要比较删除不同冲突对后的效果）。
• 但代码中似乎采用另一种思路：
  • 首先，假设我们删除某个冲突对 [a, b]（其中 a < b），那么剩余冲突对集合就是原集合去掉这一对。
  • 然后，我们需要快速计算此时合法子段的数目？但直接计算对于每个删除操作是昂贵的。
• 代码中似乎尝试高效计算删除每个冲突对后的增益（即比不删除时多出多少合法子段？），但实际代码逻辑较复杂。

4. 代码具体步骤

• 初始化 bMin1 和 bMin2 数组（长度 n+1，初始值设为很大）。
• 遍历所有冲突对，对于每个冲突对 [x, y]（令 a = min(x,y), b = max(x,y)）：
  • 如果 b 小于 bMin1[a]，则更新 bMin2[a] = bMin1[a]，bMin1[a] = b。
  • 否则如果 b 小于 bMin2[a]，则更新 bMin2[a] = b。
  • 这样，对于每个 a，bMin1[a] 是与其冲突的最小数字（大于 a），bMin2[a] 是次小的（如果存在）。
• 然后，代码从后往前遍历（从 n 到 1）：
  • 维护 ib1（当前最小冲突对起点的索引？）、b2（全局次小冲突值？）。
  • 计算 res（累计值，表示某种基础子段数？）。
  • 同时，delCount[ib1] 记录删除以 ib1 为起点的冲突对（即 [ib1, bMin1[ib1]]）所带来的额外增益（即多产生的合法子段数？）。
• 最后，res + max(delCount) 就是答案（即基础值加上删除某对冲突后的最大增益）。

5. 直观解释

• 基础值 res 可能是不删除任何冲突对时的合法子段数？但题目要求必须删除一对，所以基础值可能不是直接意义。
• 另一种解释：基础值 res 是删除某对冲突后的合法子段数的一个下界？然后 delCount[i] 表示如果删除以 i 为起点的最小冲突对（即 [i, bMin1[i]]）所能额外增加的子段数。
• 最终答案 = 基础值 + 最大额外增益。

6. 为什么这样设计？

• 冲突对中，删除一个冲突对 [a, b]（其中 a < b）后，原本因为这对冲突而不能出现的子段（即同时包含 a 和 b 的子段）现在变得合法了。
• 因此，删除一对冲突带来的增益就是：原本因为该对冲突而不合法的子段数量（这些子段现在变得合法了）。
• 但注意：剩余冲突对仍然存在，所以删除一对冲突后，合法子段数 = 总子段数（即 n*(n+1)/2）减去因为剩余冲突对而不合法的子段数？但这样计算可能复杂。
• 代码中似乎采用近似方法：只考虑每个起点 i 对应的最小冲突对 [i, bMin1[i]] 的删除增益（因为删除更大的冲突对可能增益更小？）。

7. 总结代码行为

• 预处理每个数字 i 的最小和次小冲突数字（即最“近”的冲突）。
• 从后往前扫描，维护全局最小冲突信息。
• 计算基础值 res（可能是不删除冲突对时，考虑最小冲突约束下的合法子段数？实际上可能不是，因为必须删除一对）。
• 同时，对于每个起点 i，计算删除其最小冲突对 [i, bMin1[i]] 所带来的增益（即多释放的子段数），存入 delCount[i]。
• 最终结果为 res + max(delCount)。

时间复杂度和额外空间复杂度

• 时间复杂度：O(n + m)（其中 m 是冲突对的数量）。
  • 预处理冲突对：遍历所有冲突对（O(m)）。
  • 初始化数组：O(n)。
  • 从后往前扫描：O(n)。
  • 因此总时间复杂度为 O(n + m)。
• 额外空间复杂度：O(n)。
  • 需要 bMin1、bMin2、delCount 数组，每个长度均为 n+1。
  • 因此额外空间为 O(n)。

注意：虽然冲突对数量 m 最大可能为 2*n，但预处理和扫描都是线性的，因此总时间高效。

Go完整代码如下：

package main

import (
	"fmt"
	"math"
)

func maxSubarrays(n int, conflictingPairs [][]int) int64 {
	bMin1 := make([]int, n+1)
	bMin2 := make([]int, n+1)
	for i := 0; i <= n; i++ {
		bMin1[i] = math.MaxInt32
		bMin2[i] = math.MaxInt32
	}
	for _, pair := range conflictingPairs {
		a := min(pair[0], pair[1])
		b := max(pair[0], pair[1])
		if bMin1[a] > b {
			bMin2[a] = bMin1[a]
			bMin1[a] = b
		} else if bMin2[a] > b {
			bMin2[a] = b
		}
	}
	res, ib1, b2 := int64(0), n, math.MaxInt32
	delCount := make([]int64, n+1)
	for i := n; i >= 1; i-- {
		if bMin1[ib1] > bMin1[i] {
			b2 = min(b2, bMin1[ib1])
			ib1 = i
		} else {
			b2 = min(b2, bMin1[i])
		}
		res += int64(min(bMin1[ib1], n+1) - i)
		delCount[ib1] += int64(min(min(b2, bMin2[ib1]), n+1) - min(bMin1[ib1], n+1))
	}
	maxVal := int64(0)
	for _, v := range delCount {
		maxVal = max(maxVal, v)
	}
	return res + maxVal
}

func main() {
	n := 4
	conflictingPairs := [][]int{{2, 3}, {1, 4}}
	result := maxSubarrays(n, conflictingPairs)
	fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

def max_subarrays(n: int, conflictingPairs: list[list[int]]) -> int:
    INF = 10**18
    bMin1 = [INF] * (n + 1)
    bMin2 = [INF] * (n + 1)

    # 记录每个 a 对应的最小和次小的 b
    for pair in conflictingPairs:
        a = min(pair[0], pair[1])
        b = max(pair[0], pair[1])
        if bMin1[a] > b:
            bMin2[a] = bMin1[a]
            bMin1[a] = b
        elif bMin2[a] > b:
            bMin2[a] = b

    res = 0
    ib1 = n
    b2 = INF
    delCount = [0] * (n + 1)

    # 从右向左遍历，复刻原 Go 逻辑
    for i in range(n, 0, -1):
        if bMin1[ib1] > bMin1[i]:
            b2 = min(b2, bMin1[ib1])
            ib1 = i
        else:
            b2 = min(b2, bMin1[i])

        res += min(bMin1[ib1], n + 1) - i
        delCount[ib1] += min(min(b2, bMin2[ib1]), n + 1) - min(bMin1[ib1], n + 1)

    maxVal = max(delCount)
    return res + maxVal

if __name__ == "__main__":
    n = 4
    conflictingPairs = [[2, 3], [1, 4]]
    print(max_subarrays(n, conflictingPairs))