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.hlong 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 结尾的合法子数组数量左端点必须 maxLeftvalidSubarrays (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)该解法通过一次线性扫描完成无需排序效率最优。
)
