以下是 LeetCode 3510. 移除最小数对使数组有序 II 的 C++ 实现。

解题思路

这道题的核心是模拟 + 贪心，但直接暴力模拟会超时（O(n^2)），需要优化到 O(n \log n)。

关键优化点：

1. 双向链表 — 用 `nxt[]` / `prv[]` 数组模拟双向链表，合并相邻节点只需修改指针，O(1) 完成，避免数组删除的 O(n) 开销。
2. 最小堆（优先队列） — `priority_queue` 配合 `greater<>` 实现小根堆，维护所有相邻对的和，每次快速取出最小和的配对，O(\log n)。
3. 逆序对计数 — 维护当前相邻逆序对的数量，当计数为 0 时数组已非递减，无需全量扫描。每次合并只更新局部受影响的逆序对。
4. 懒惰删除 — 堆中可能存在过期条目（节点已被合并），弹出时校验有效性，无效则跳过。

算法流程：
- 初始化双向链表、逆序对计数、最小堆
- 当逆序对 > 0 时循环：
  - 从堆中取出最小和配对（跳过无效条目）
  - 减去合并前涉及的逆序对
  - 合并节点（左节点值更新为和，右节点删除）
  - 加上合并后新增的逆序对
  - 将新的相邻对推入堆

---

C++ 代码

```cpp
#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int minimumPairRemoval(vector<int>& nums) {
        int n = nums.size();
        if (n <= 1) return 0;

        // vals[i] stores current value at node i (use long long to prevent overflow)
        vector<long long> vals(n);
        for (int i = 0; i < n; ++i) vals[i] = nums[i];

        // next[i] / prev[i] simulate doubly linked list, -1 means none
        vector<int> nxt(n), prv(n);
        for (int i = 0; i < n; ++i) nxt[i] = (i + 1 < n) ? i + 1 : -1;
        for (int i = 0; i < n; ++i) prv[i] = (i - 1 >= 0) ? i - 1 : -1;

        // removed[i] marks if node i has been merged/deleted
        vector<bool> removed(n, false);

        // Count initial inversions (adjacent pairs where nums[i] > nums[i+1])
        int invCount = 0;
        for (int i = 0; i < n - 1; ++i) {
            if (vals[i] > vals[i + 1]) ++invCount;
        }
        if (invCount == 0) return 0;

        // Min-heap: (sum of adjacent pair, left node index)
        // Use greater<> for min-heap (default is max-heap)
        using T = pair<long long, int>;
        priority_queue<T, vector<T>, greater<T>> heap;
        for (int i = 0; i < n - 1; ++i) {
            heap.emplace(vals[i] + vals[i + 1], i);
        }

        int ops = 0;

        while (invCount > 0 && !heap.empty()) {
            auto [sum, u] = heap.top(); heap.pop();

            // Lazy deletion: skip if left node already removed
            if (removed[u]) continue;

            int v = nxt[u];
            // Skip if right node doesn't exist, is removed, or sum doesn't match
            if (v == -1 || removed[v] || vals[u] + vals[v] != sum) continue;

            int p = prv[u];
            int nv = nxt[v];
            ++ops;

            // 1. Subtract inversions before merge
            if (p != -1 && vals[p] > vals[u]) --invCount;   // (p, u)
            if (vals[u] > vals[v]) --invCount;               // (u, v)
            if (nv != -1 && vals[v] > vals[nv]) --invCount;  // (v, nv)

            // 2. Perform merge: update left node to sum, delete right node
            vals[u] = sum;
            nxt[u] = nv;
            if (nv != -1) prv[nv] = u;
            removed[v] = true;

            // 3. Add inversions after merge
            if (p != -1 && vals[p] > vals[u]) ++invCount;   // (p, u) with new sum
            if (nv != -1 && vals[u] > vals[nv]) ++invCount;  // (u, nv) with new sum

            // 4. Push new adjacent pairs into heap
            if (p != -1) heap.emplace(vals[p] + vals[u], p);
            if (nv != -1) heap.emplace(vals[u] + vals[nv], u);
        }

        return ops;
    }
};
```

---

复杂度分析

项目    复杂度    
时间    O(n \log n) — 每个节点最多被合并一次，每次堆操作 O(\log n)    
空间    O(n) — 链表数组 + 堆 + 标记数组    

---

示例验证

输入    输出    说明    
`[5, 2, 3, 1]`    `2`    先合并 `(3,1)→4`，再合并 `(2,4)→6`，得 `[5,6]`    
`[1, 2, 2]`    `0`    已有序    
`[100001, -100000, 1, 0]`    `3`    边界情况    

---

下载文件：[leetcode_3510.cpp](sandbox:///mnt/agents/output/leetcode_3510.cpp)