Hard

题目描述

给你一个整数 n，表示一个数组 nums，该数组包含从 1 到 n 的数字（按顺序排列）。另外，给你一个二维数组 conflictingPairs，其中 conflictingPairs[i] = [a, b] 表示 a 和 b 构成一个冲突对。

从 conflictingPairs 中恰好删除一个元素。之后，计算 nums 的非空子数组的数量，这些子数组不包含任何剩余冲突对 [a, b] 中的 a 和 b。

返回删除恰好一个冲突对后可能的最大子数组数量。

示例 1：

输入：n = 4, conflictingPairs = [[2,3],[1,4]]
输出：9
解释：
从 conflictingPairs 中删除 [2, 3]。现在，conflictingPairs = [[1, 4]]。
在 nums 中有 9 个子数组，其中 [1, 4] 不同时出现。它们是 [1], [2], [3], [4], [1, 2], [2, 3], [3, 4], [1, 2, 3] 和 [2, 3, 4]。
从 conflictingPairs 中删除一个元素后可以获得的最大子数组数量是 9。

示例 2：

输入：n = 5, conflictingPairs = [[1,2],[2,5],[3,5]]
输出：12
解释：
从 conflictingPairs 中删除 [1, 2]。现在，conflictingPairs = [[2, 5], [3, 5]]。
有 12 个子数组，其中 [2, 5] 和 [3, 5] 不同时出现。
从 conflictingPairs 中删除一个元素后可以获得的最大子数组数量是 12。

约束条件：

  • 2 <= n <= 10^5
  • 1 <= conflictingPairs.length <= 2 * n
  • conflictingPairs[i].length == 2
  • 1 <= conflictingPairs[i][j] <= n
  • conflictingPairs[i][0] != conflictingPairs[i][1]

解题思路

这道题的核心思想是计算删除每个冲突对后的有效子数组数量，然后取最大值。

解题思路：

  1. 理解问题：对于数组 [1,2,…,n]，我们需要计算不包含任何冲突对的子数组数量。冲突对 [a,b] 意味着子数组不能同时包含 a 和 b。

  2. 关键观察：如果我们知道每个位置 i 开始的最长有效子数组的结束位置 f[i]，那么从位置 i 开始的有效子数组数量就是 f[i] - i + 1。

  3. 算法步骤：

    • 对于每个可能删除的冲突对，计算剩余冲突对约束下的 f[i] 数组
    • 使用贪心策略：对于冲突对 (x,y) 其中 x < y，从位置 1 到 x-1 都可以延伸到 y-1，从位置 x 开始则最多延伸到 y-1
    • 总的有效子数组数量 = Σ(f[i] - i + 1) = Σf[i] - n*(n+1)/2 + n

  4. 优化：

    • 按照冲突对的右端点降序排列处理
    • 使用线段树或差分数组进行区间更新和求和
    • 对每个删除情况计算结果，取最大值

时间复杂度优化：通过合理的数据结构维护 f 数组，可以达到较好的时间复杂度。

代码实现

class Solution {
public:
    long long maxSubarrays(int n, vector<vector<int>>& conflictingPairs) {
        int m = conflictingPairs.size();
        long long maxResult = 0;
        
        for (int remove = 0; remove < m; remove++) {
            vector<int> f(n + 1, n);
            
            for (int i = 0; i < m; i++) {
                if (i == remove) continue;
                
                int x = conflictingPairs[i][0];
                int y = conflictingPairs[i][1];
                if (x > y) swap(x, y);
                
                for (int j = x; j <= n; j++) {
                    f[j] = min(f[j], y - 1);
                }
            }
            
            long long sum = 0;
            for (int i = 1; i <= n; i++) {
                sum += f[i] - i + 1;
            }
            
            maxResult = max(maxResult, sum);
        }
        
        return maxResult;
    }
};

class Solution:
    def maxSubarrays(self, n: int, conflictingPairs: List[List[int]]) -> int:
        m = len(conflictingPairs)
        max_result = 0
        
        for remove in range(m):
            f = [n] * (n + 1)
            
            for i in range(m):
                if i == remove:
                    continue
                
                x, y = conflictingPairs[i]
                if x > y:
                    x, y = y, x
                
                for j in range(x, n + 1):
                    f[j] = min(f[j], y - 1)
            
            total = sum(f[i] - i + 1 for i in range(1, n + 1))
            max_result = max(max_result, total)
        
        return max_result

public class Solution {
    public long MaxSubarrays(int n, int[][] conflictingPairs) {
        int m = conflictingPairs.Length;
        long maxResult = 0;
        
        for (int remove = 0; remove < m; remove++) {
            int[] f = new int[n + 1];
            Array.Fill(f, n);
            
            for (int i = 0; i < m; i++) {
                if (i == remove) continue;
                
                int x = conflictingPairs[i][0];
                int y = conflictingPairs[i][1];
                if (x > y) {
                    int temp = x;
                    x = y;
                    y = temp;
                }
                
                for (int j = x; j <= n; j++) {
                    f[j] = Math.Min(f[j], y - 1);
                }
            }
            
            long sum = 0;
            for (int i = 1; i <= n; i++) {
                sum += f[i] - i + 1;
            }
            
            maxResult = Math.Max(maxResult, sum);
        }
        
        return maxResult;
    }
}

var maxSubarrays = function(n, conflictingPairs) {
    function countValidSubarrays(pairs) {
        let segments = [];
        let start = 1;
        
        for (let i = 1; i <= n; i++) {
            let hasConflict = false;
            for (let [a, b] of pairs) {
                if ((a <= start && b <= i && a <= i && b >= start) || 
                    (b <= start && a <= i && b <= i && a >= start)) {
                    hasConflict = true;
                    break;
                }
            }
            
            if (hasConflict) {
                if (i > start) {
                    segments.push(i - start);
                }
                start = i + 1;
            }
        }
        
        if (start <= n) {
            segments.push(n - start + 1);
        }
        
        let total = 0;
        for (let len of segments) {
            total += (len * (len + 1)) / 2;
        }
        
        return total;
    }
    
    function countValidSubarraysOptimized(pairs) {
        let breakPoints = new Set();
        
        for (let [a, b] of pairs) {
            let left = Math.min(a, b);
            let right = Math.max(a, b);
            
            for (let i = left; i < right; i++) {
                for (let j = i + 1; j <= right; j++) {
                    if ((i < left || i > right || j < left || j > right) === false) {
                        if (i <= left && j >= right) {
                            breakPoints.add(i);
                            breakPoints.add(j);
                        }
                    }
                }
            }
        }
        
        let positions = [];
        for (let [a, b] of pairs) {
            for (let i = Math.min(a, b); i <= Math.max(a, b); i++) {
                positions.push(i);
            }
        }
        
        let segments = [];
        let start = 1;
        
        for (let end = 1; end <= n; end++) {
            let valid = true;
            
            for (let [a, b] of pairs) {
                let left = Math.min(a, b);
                let right = Math.max(a, b);
                
                if (start <= left && end >= right) {
                    valid = false;
                    break;
                }
            }
            
            if (!valid) {
                if (end > start) {
                    let segLen = end - start;
                    if (segLen > 0) segments.push(segLen);
                }
                start = end + 1;
            }
        }
        
        if (start <= n) {
            segments.push(n - start + 1);
        }
        
        let total = 0;
        for (let len of segments) {
            total += (len * (len + 1)) / 2;
        }
        
        return total;
    }
    
    function countValidSubarraysCorrect(pairs) {
        let total = 0;
        
        for (let i = 1; i <= n; i++) {
            for (let j = i; j <= n; j++) {
                let valid = true;
                
                for (let [a, b] of pairs) {
                    if (i <= a && a <= j && i <= b && b <= j) {
                        valid = false;
                        break;
                    }
                }
                
                if (valid) {
                    total++;
                }
            }
        }
        
        return total;
    }
    
    let maxCount = 0;
    
    for (let removeIdx = 0; removeIdx < conflictingPairs.length; removeIdx++) {
        let remainingPairs = conflictingPairs.filter((_, idx) => idx !== removeIdx);
        let count = countValidSubarraysCorrect(remainingPairs);
        maxCount = Math.max(maxCount, count);
    }
    
    return maxCount;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(m²n) 其中 m 是冲突对数量，n 是数组长度
空间复杂度O(n) 用于存储 f 数组