Kimi LeetCode 3480. 删除一个冲突对后最大子数组数目 C语言实现

以下是 LeetCode 3480 删除一个冲突对后最大子数组数目 的 C 语言实现。

思路

核心思路是枚举子数组右端点，维护当前最严格和次严格的冲突限制：

1. 预处理：将每个冲突对 `(a, b)` 按较大值（即右端点）分组。对于子数组右端点 `right`，所有较大值为 `right` 的冲突对都会在此刻生效。
2. 维护两个关键变量：
- `maxLeft`：所有已生效冲突对中最大的左端点。以 `right` 结尾的合法子数组，其左端点必须 `> maxLeft`，因此贡献 `right - maxLeft` 个合法子数组。
- `secondMaxLeft`：次大的左端点。如果删除 `maxLeft` 对应的那个冲突对，限制会放宽到 `secondMaxLeft`，此时能多获得 `maxLeft - secondMaxLeft` 个子数组。
3. 记录收益：用 `gains[left]` 数组记录“如果删除那个使 `maxLeft` 达到 `left` 的冲突对”所能获得的总额外子数组数。
4. 最终答案：`合法子数组总数 + max(gains)`

时间复杂度 O(n + m)，空间复杂度 O(n + m)。

C 代码

```c
#include <stdlib.h>

long long maxSubarrays(int n, int** conflictingPairs, int conflictingPairsSize, int* conflictingPairsColSize) {
// ---------- 1. 按冲突对的较大值（右端点）分组 ----------
int* cnt = (int*)calloc(n + 1, sizeof(int));
for (int i = 0; i < conflictingPairsSize; i++) {
int a = conflictingPairs[i][0];
int b = conflictingPairs[i][1];
int mx = a > b ? a : b; // 较大值作为右端点
cnt[mx]++;
}

// 分配二维数组 conflicts[right] 存储所有左端点
int** conflicts = (int**)malloc((n + 1) * sizeof(int*));
for (int i = 0; i <= n; i++) {
conflicts[i] = (int*)malloc(cnt[i] * sizeof(int));
}

int* idx = (int*)calloc(n + 1, sizeof(int));
for (int i = 0; i < conflictingPairsSize; i++) {
int a = conflictingPairs[i][0];
int b = conflictingPairs[i][1];
int mx = a > b ? a : b;
int mn = a < b ? a : b; // 较小值作为左端点
conflicts[mx][idx[mx]++] = mn;
}

// ---------- 2. 枚举右端点，计算合法子数组和删除收益 ----------
long long validSubarrays = 0;
int maxLeft = 0; // 当前最严格的冲突左端点
int secondMaxLeft = 0; // 次严格的冲突左端点
long long* gains = (long long*)calloc(n + 1, sizeof(long long));

for (int right = 1; right <= n; right++) {
// 加入所有以 right 为较大值的冲突对
for (int j = 0; j < cnt[right]; j++) {
int left = conflicts[right][j];
if (left > maxLeft) {
secondMaxLeft = maxLeft;
maxLeft = left;
} else if (left > secondMaxLeft) {
secondMaxLeft = left;
}
}

// 以 right 结尾的合法子数组数量：左端点必须 > maxLeft
validSubarrays += (long long)(right - maxLeft);

// 若删除当前 maxLeft 对应的冲突对，能多获得的子数组数
gains[maxLeft] += (long long)(maxLeft - secondMaxLeft);
}

// ---------- 3. 找到删除一个冲突对后的最大收益 ----------
long long maxGain = 0;
for (int i = 0; i <= n; i++) {
if (gains[i] > maxGain) {
maxGain = gains[i];
}
}

// 释放内存（LeetCode 不强制要求，但良好习惯）
free(cnt);
free(idx);
for (int i = 0; i <= n; i++) {
free(conflicts[i]);
}
free(conflicts);
free(gains);

return validSubarrays + maxGain;
}
```

复杂度分析

指标 复杂度
时间 O(n + m)，其中 `m = conflictingPairsSize`
空间 O(n + m)

该解法通过一次线性扫描完成，无需排序，效率最优。