企业官网建设流程全解析

以下是 LeetCode 3510. Minimum Pair Removal to Sort Array II 的 Java 实现。

解题思路

这道题的核心挑战在于将时间复杂度从 O(n²) 优化到 O(n log n)：

1. 最小相邻对查找：使用 `TreeSet`（平衡二叉搜索树）维护所有相邻元素对的和，支持 O(log n) 的插入、删除和取最小值操作。

2. 有序性判断：不每次扫描整个数组判断有序，而是维护一个 `inversionsCount`（逆序对计数）。当 `inversionsCount == 0` 时，数组即为非递减序列。

3. 链表式数组维护：使用 `nextIndices` 和 `prevIndices` 数组模拟双向链表，实现 O(1) 的"删除"操作（逻辑删除，不实际移动数组元素）。

每次合并操作只会影响当前节点的前一个和后一个相邻对，因此只需局部更新 `TreeSet` 和逆序计数。

Java 代码

```java
import java.util.*;

class Solution {
public int minimumPairRemoval(int[] nums) {
final int n = nums.length;
int ans = 0;
int inversionsCount = 0;

// 模拟双向链表：nextIndices[i] 表示 i 的下一个有效元素的下标
int[] nextIndices = new int[n];
int[] prevIndices = new int[n];
// 用 long 存储值，防止两个 int 相加溢出
long[] values = new long[n];
for (int i = 0; i < n; i++) {
values[i] = nums[i];
}

// TreeSet 维护所有相邻对的 (和, 左端点下标)
// 按和升序，和相同则按下标升序（保证取最左边的对）
TreeSet<long[]> pairSums = new TreeSet<>((a, b) -> {
if (a[0] != b[0]) return Long.compare(a[0], b[0]);
return Long.compare(a[1], b[1]);
});

// 初始化链表
for (int i = 0; i < n; i++) {
nextIndices[i] = i + 1;
prevIndices[i] = i - 1;
}

// 初始化所有相邻对的和
for (int i = 0; i < n - 1; i++) {
pairSums.add(new long[]{values[i] + values[i + 1], i});
}

// 初始化逆序对计数
for (int i = 0; i < n - 1; i++) {
if (nums[i + 1] < nums[i]) {
inversionsCount++;
}
}

// 当还有逆序对时，继续合并
while (inversionsCount > 0) {
ans++;

// 取出和最小的相邻对
long[] smallestPair = pairSums.pollFirst();
long pairSum = smallestPair[0];
int currIndex = (int) smallestPair[1];
int nextIndex = nextIndices[currIndex];
int prevIndex = prevIndices[currIndex];

// 更新前一个相邻对
if (prevIndex >= 0) {
long oldPairSum = values[prevIndex] + values[currIndex];
long newPairSum = values[prevIndex] + pairSum;
pairSums.remove(new long[]{oldPairSum, prevIndex});
pairSums.add(new long[]{newPairSum, prevIndex});

// 更新逆序计数：原来的 (prev, curr) 对
if (values[prevIndex] > values[currIndex]) {
inversionsCount--;
}
// 新的 (prev, curr+next) 对
if (values[prevIndex] > pairSum) {
inversionsCount++;
}
}

// 当前 (curr, next) 这对的逆序关系消失
if (values[nextIndex] < values[currIndex]) {
inversionsCount--;
}

// 更新后一个相邻对
int nextNextIndex = (nextIndex < n) ? nextIndices[nextIndex] : n;
if (nextNextIndex < n) {
long oldPairSum = values[nextIndex] + values[nextNextIndex];
long newPairSum = pairSum + values[nextNextIndex];
pairSums.remove(new long[]{oldPairSum, nextIndex});
pairSums.add(new long[]{newPairSum, currIndex});

// 原来的 (next, nextNext) 对
if (values[nextNextIndex] < values[nextIndex]) {
inversionsCount--;
}
// 新的 (curr+next, nextNext) 对
if (values[nextNextIndex] < pairSum) {
inversionsCount++;
}
// 链表连接：currIndex 的下一个变为 nextNextIndex
prevIndices[nextNextIndex] = currIndex;
}

// 更新链表和值
nextIndices[currIndex] = nextNextIndex;
values[currIndex] = pairSum;
}

return ans;
}
}
```

复杂度分析

- 时间复杂度：O(n log n)。每次操作涉及常数次 `TreeSet` 的插入/删除（O(log n)），最多执行 n-1 次合并。
- 空间复杂度：O(n)。用于存储链表指针、值数组和 `TreeSet`。