LeetCode 3480. 删除一个冲突对后最大子数组数目 — Java 实现题目大意给定整数 n数组 nums 为 1 到 n以及冲突对列表 conflictingPairs。要求恰好删除一个冲突对使得剩余数组中不包含任何冲突对的子数组数量最大返回这个最大值。核心思路枚举左端点 维护最小/次小值1. 预处理对每个冲突对 (a, b)保证 a b将 b 存入 groups[a] 中。2. 倒序枚举左端点 a从 n 到 1维护当前所有满足条件的冲突对中- b0最小的 b 值- b1次小的 b 值3. 基础贡献左端点为 a 时合法右端点范围是 [a, b0-1]贡献为 b0 - a。4. 删除贡献若删除的冲突对恰好使得最小值从 b0 变成 b1则额外增加 b1 - b0 个合法子数组。用 extra[b0] 累加所有该 b0 对应的额外贡献。5. 最终答案基础答案 max(extra)。时间复杂度 O(n)空间复杂度 O(n)。---Java 代码javaclass Solution {public long maxSubarrays(int n, int[][] conflictingPairs) {// groups[a] 存储所有以 a 为左端点a b的冲突对的 b 值ListInteger[] groups new ArrayList[n 1];for (int i 0; i n; i) {groups[i] new ArrayList();}for (int[] p : conflictingPairs) {int a p[0], b p[1];if (a b) {int tmp a;a b;b tmp;}groups[a].add(b);}long ans 0; // 不删除任何冲突对时的合法子数组数量long[] extra new long[n 2]; // extra[b0] 表示删除导致最小值为 b0 的冲突对后的额外贡献long maxExtra 0;int b0 n 1; // 当前最小 bint b1 n 1; // 当前次小 b// 倒序枚举左端点for (int a n; a 1; a--) {// 用 groups[a] 中的 b 值更新 b0 和 b1for (int b : groups[a]) {if (b b0) {b1 b0;b0 b;} else if (b b1) {b1 b;}}// 左端点为 a 时的基础贡献ans b0 - a;// 如果删除使得 b0 变成 b1 的冲突对额外贡献为 b1 - b0if (b0 n) {extra[b0] b1 - b0;maxExtra Math.max(maxExtra, extra[b0]);}}return ans maxExtra;}}---代码解释变量 含义groups[a] 所有左端点为 a且 a b的冲突对的右端点 b 的集合b0 当前所有满足 x a 的冲突对中最小的 b 值b1 当前次小的 b 值ans 不删除任何冲突对时的总合法子数组数extra[b0] 删除某个导致当前最小值为 b0 的冲突对后所有左端点的额外贡献之和为什么倒序枚举从右往左枚举左端点 a 时所有 x a 的冲突对都已经被加入因此 b0 和 b1 自然就是满足条件的全局最小和次小值。为什么 extra[b0] 用 b0 做索引对于不同的左端点 a如果它们当前的最小值 b0 相同说明删除同一个冲突对即导致这个 b0 的冲突对可以让它们同时受益因此累加到同一个 extra[b0] 中。