企业官网建设流程全解析

LeetCode 3480. 删除一个冲突对后最大子数组数目 — Python3 实现

```python
from typing import List

class 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, a
groups[a].append(b)

ans = 0 # 不删除任何冲突对时的合法子数组数量
extra = [0] * (n + 2) # extra[b0] 表示删除导致最小值为 b0 的冲突对后的额外贡献
maxExtra = 0

b0 = n + 1 # 当前最小 b
b1 = n + 1 # 当前次小 b

# 倒序枚举左端点
for a in range(n, 0, -1):
# 用 groups[a] 中的 b 值更新 b0 和 b1
for b in groups[a]:
if b < b0:
b1 = b0
b0 = b
elif b < b1:
b1 = b

# 左端点为 a 时的基础贡献
ans += b0 - a

# 如果删除使得 b0 变成 b1 的冲突对，额外贡献为 b1 - b0
if b0 <= n:
extra[b0] += b1 - b0
maxExtra = 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)`