LeetCode 3480. 删除一个冲突对后最大子数组数目 — Python3 实现pythonfrom typing import Listclass Solution:def maxSubarrays(self, n: int, conflictingPairs: List[List[int]]) - int:# groups[a] 存储所有以 a 为左端点a b的冲突对的 b 值groups [[] for _ in range(n 1)]for a, b in conflictingPairs:if a b:a, b b, agroups[a].append(b)ans 0 # 不删除任何冲突对时的合法子数组数量extra [0] * (n 2) # extra[b0] 表示删除导致最小值为 b0 的冲突对后的额外贡献maxExtra 0b0 n 1 # 当前最小 bb1 n 1 # 当前次小 b# 倒序枚举左端点for a in range(n, 0, -1):# 用 groups[a] 中的 b 值更新 b0 和 b1for b in groups[a]:if b b0:b1 b0b0 belif b b1:b1 b# 左端点为 a 时的基础贡献ans b0 - a# 如果删除使得 b0 变成 b1 的冲突对额外贡献为 b1 - b0if b0 n:extra[b0] b1 - b0maxExtra max(maxExtra, extra[b0])return ans maxExtra---核心思路步骤 说明预处理 对每个冲突对 (a, b) 保证 a b将 b 存入 groups[a]倒序枚举 从 n 到 1 枚举左端点 a此时所有 x ≥ a 的冲突对都已入队维护双最值 b0最小右端点、b1次小右端点基础贡献 左端点为 a 时合法右端点范围 [a, b0-1]贡献 b0 - a删除贡献 若删除导致 b0 的冲突对最小值升为 b1额外增加 b1 - b0累加取最大 同个 b0 可能对应多个左端点的额外贡献用 extra[b0] 累加后取全局最大时间复杂度O(n m)m 为冲突对数量空间复杂度O(n m)
