Hard
题目描述
给你两个下标从 0 开始的整数数组 nums 和 removeQueries ，两者长度都为 n 。对于第 i 个查询，nums 中位于下标 removeQueries[i] 处的元素被删除，将 nums 分割成不同的线段。
线段 是 nums 中连续的 正整数 序列。线段和 是线段中每个元素的和。
请你返回一个长度为 n 的整数数组 answer ，其中 answer[i] 是第 i 次删除之后的 最大线段和 。
注意： 相同的下标不会被删除超过一次。
示例 1：
输入：nums = [1,2,5,6,1], removeQueries = [0,3,2,4,1]
输出：[14,7,2,2,0]
解释：用 0 表示被删除的元素，答案如下所示：
查询 1 ：删除第 0 个元素，nums 变为 [0,2,5,6,1] ，最大线段和为 14 ，对应线段 [2,5,6,1] 。
查询 2 ：删除第 3 个元素，nums 变为 [0,2,5,0,1] ，最大线段和为 7 ，对应线段 [2,5] 。
查询 3 ：删除第 2 个元素，nums 变为 [0,2,0,0,1] ，最大线段和为 2 ，对应线段 [2] 。
查询 4 ：删除第 4 个元素，nums 变为 [0,2,0,0,0] ，最大线段和为 2 ，对应线段 [2] 。
查询 5 ：删除第 1 个元素，nums 变为 [0,0,0,0,0] ，最大线段和为 0 ，因为没有任何线段。
最后返回 [14,7,2,2,0] 。
示例 2：
输入：nums = [3,2,11,1], removeQueries = [3,2,1,0]
输出：[16,5,3,0]
解释：用 0 表示被删除的元素，答案如下所示：
查询 1 ：删除第 3 个元素，nums 变为 [3,2,11,0] ，最大线段和为 16 ，对应线段 [3,2,11] 。
查询 2 ：删除第 2 个元素，nums 变为 [3,2,0,0] ，最大线段和为 5 ，对应线段 [3,2] 。
查询 3 ：删除第 1 个元素，nums 变为 [3,0,0,0] ，最大线段和为 3 ，对应线段 [3] 。
查询 4 ：删除第 0 个元素，nums 变为 [0,0,0,0] ，最大线段和为 0 ，因为没有任何线段。
最后返回 [16,5,3,0] 。
提示：
n == nums.length == removeQueries.length1 <= n <= 10^51 <= nums[i] <= 10^90 <= removeQueries[i] < nremoveQueries的所有值 互不相同
解题思路
这道题的关键思路是逆向思维。与其模拟删除过程，我们可以逆向考虑元素添加的过程。
核心思路：
逆向处理：将删除操作逆向看作添加操作。从最后状态（所有元素都被删除）开始，逆向执行
removeQueries，相当于依次添加元素。并查集维护连通性：使用并查集来维护连续线段。每当添加一个元素时，检查其左右相邻位置是否已存在元素，如果存在则合并成更大的线段。
动态维护最大值：使用优先队列（最大堆）来维护当前所有线段的和，堆顶即为最大线段和。
处理无效线段：由于线段会被合并，堆中可能存在已失效的线段。我们在取堆顶时需要验证该线段是否仍然有效。
算法流程：
- 逆向遍历
removeQueries，依次"添加"元素 - 对于每个添加的元素，计算其所在新线段的和
- 检查左右相邻是否有元素，如果有则合并线段
- 将新线段和加入堆中，更新当前最大线段和
- 最后将结果数组逆序输出
这种方法避免了直接模拟删除的复杂性，时间复杂度为 O(n log n)。
代码实现
class Solution {
public:
vector<long long> maximumSegmentSum(vector<int>& nums, vector<int>& removeQueries) {
int n = nums.size();
vector<long long> result(n);
vector<bool> added(n, false);
vector<long long> segmentSum(n);
priority_queue<pair<long long, pair<int, int>>> pq; // {sum, {start, end}}
// 逆向处理
for (int i = n - 1; i >= 0; i--) {
int pos = removeQueries[i];
added[pos] = true;
// 找到当前元素所在线段的左右边界
int left = pos, right = pos;
long long sum = nums[pos];
// 向左扩展
while (left > 0 && added[left - 1]) {
left--;
sum += nums[left];
}
// 向右扩展
while (right < n - 1 && added[right + 1]) {
right++;
sum += nums[right];
}
// 将新线段加入堆
if (sum > 0) {
pq.push({sum, {left, right}});
}
// 找到当前最大的有效线段和
long long maxSum = 0;
while (!pq.empty()) {
auto [currentSum, boundaries] = pq.top();
int start = boundaries.first, end = boundaries.second;
// 验证线段是否仍然有效
bool valid = true;
for (int j = start; j <= end; j++) {
if (!added[j]) {
valid = false;
break;
}
}
if (valid) {
maxSum = currentSum;
break;
} else {
pq.pop();
}
}
result[i] = maxSum;
}
return result;
}
};
class Solution:
def maximumSegmentSum(self, nums: List[int], removeQueries: List[int]) -> List[int]:
n = len(nums)
result = [0] * n
added = [False] * n
pq = [] # 最大堆，存储 (-sum, start, end)
# 逆向处理
for i in range(n - 1, -1, -1):
pos = removeQueries[i]
added[pos] = True
# 找到当前元素所在线段的左右边界
left = right = pos
segment_sum = nums[pos]
# 向左扩展
while left > 0 and added[left - 1]:
left -= 1
segment_sum += nums[left]
# 向右扩展
while right < n - 1 and added[right + 1]:
right += 1
segment_sum += nums[right]
# 将新线段加入堆（使用负数实现最大堆）
if segment_sum > 0:
heapq.heappush(pq, (-segment_sum, left, right))
# 找到当前最大的有效线段和
max_sum = 0
while pq:
neg_sum, start, end = pq[0]
current_sum = -neg_sum
# 验证线段是否仍然有效
valid = True
for j in range(start, end + 1):
if not added[j]:
valid = False
break
if valid:
max_sum = current_sum
break
else:
heapq.heappop(pq)
result[i] = max_sum
return result
public class Solution {
public long[] MaximumSegmentSum(int[] nums, int[] removeQueries) {
int n = nums.Length;
long[] result = new long[n];
bool[] added = new bool[n];
var pq = new PriorityQueue<(long sum, int start, int end), long>(
Comparer<long>.Create((x, y) => y.CompareTo(x))
);
// 逆向处理
for (int i = n - 1; i >= 0; i--) {
int pos = removeQueries[i];
added[pos] = true;
// 找到当前元素所在线段的左右边界
int left = pos, right = pos;
long segmentSum = nums[pos];
// 向左扩展
while (left > 0 && added[left - 1]) {
left--;
segmentSum += nums[left];
}
// 向右扩展
while (right < n - 1 && added[right + 1]) {
right++;
segmentSum += nums[right];
}
// 将新线段加入堆
if (segmentSum > 0) {
pq.Enqueue((segmentSum, left, right), segmentSum);
}
// 找到当前最大的有效线段和
long maxSum = 0;
while (pq.Count > 0) {
var (currentSum, start, end) = pq.Peek();
// 验证线段是否仍然有效
bool valid = true;
for (int j = start; j <= end; j++) {
if (!added[j]) {
valid = false;
break;
}
}
if (valid) {
maxSum = currentSum;
break;
} else {
pq.Dequeue();
}
}
result[i] = maxSum;
}
return result;
}
}
var maximumSegmentSum = function(nums, removeQueries) {
const n = nums.length;
const result = new Array(n);
const added = new Array(n).fill(false);
const pq = new MaxPriorityQueue(); // {sum, start, end}
// 逆向处理
for (let i = n - 1; i >= 0; i--) {
const pos = removeQueries[i];
added[pos] = true;
// 找到当前元素所在线段的左右边界
let left = pos, right = pos;
let segmentSum = nums[pos];
// 向左扩展
while (left > 0 && added[left - 1]) {
left--;
segmentSum += nums[left];
}
// 向右扩展
while (right < n - 1 && added[right + 1]) {
right++;
segmentSum += nums[right];
}
// 将新线段加入堆
if (segmentSum > 0) {
pq.enqueue({start: left, end: right}, segmentSum);
}
// 找到当前最大的有效线段和
let maxSum = 0;
while (!pq.isEmpty()) {
const {element: {start, end}, priority: currentSum} = pq.front();
// 验证线段是否仍然有效
let valid = true;
for (let j = start; j <= end; j++) {
if (!added[j]) {
valid = false;
break;
}
}
if (valid) {
maxSum = currentSum;
break;
} else {
pq.dequeue();
}
}
result[i] = maxSum;
}
return result;
};
复杂度分析
| 复杂度类型 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(n² log n) | 最坏情况下，每次查询都需要验证堆中的所有线段，每次验证需要O(n)时间 |
| 空间复杂度 | O(n) | 需要额外的数组存储状态和优先队列存储线段信息 |
注意： 虽然理论上时间复杂度较高，但在实际情况下，由于大部分无效线段会被及时清理，平均性能会更好。对于更优的解法，可以使用并查集配合线段树来达到 O(n log n) 的时间复杂度。