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

解题思路

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

关键优化点：

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

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

---

Rust 代码

```rust
use std::cmp::Reverse;
use std::collections::BinaryHeap;

struct Solution;

impl Solution {
    pub fn minimum_pair_removal(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        if n <= 1 {
            return 0;
        }

        // vals[i] 存储当前节点 i 的值（用 i64 防止溢出）
        let mut vals: Vec<i64> = nums.into_iter().map(|x| x as i64).collect();
        
        // next[i] / prev[i] 模拟双向链表，-1 表示无
        let mut next: Vec<i32> = (0..n as i32).map(|i| i + 1).collect();
        next[n - 1] = -1;
        let mut prev: Vec<i32> = (0..n as i32).map(|i| i - 1).collect();
        
        // 标记节点是否已被合并删除
        let mut removed: Vec<bool> = vec![false; n];

        // 统计初始逆序对数量
        let mut inv_count = 0i32;
        for i in 0..n - 1 {
            if vals[i] > vals[i + 1] {
                inv_count += 1;
            }
        }
        if inv_count == 0 {
            return 0;
        }

        // 最小堆：(相邻元素和, 左节点索引)
        let mut heap: BinaryHeap<Reverse<(i64, i32)>> = BinaryHeap::new();
        for i in 0..n - 1 {
            heap.push(Reverse((vals[i] + vals[i + 1], i as i32)));
        }

        let mut ops = 0i32;

        while inv_count > 0 && !heap.is_empty() {
            let Reverse((sum, u)) = heap.pop().unwrap();
            
            // 懒惰删除：左节点已被删除则跳过
            if removed[u as usize] {
                continue;
            }
            
            let v = next[u as usize];
            // 右节点不存在 / 已删除 / 和不匹配 → 过期条目
            if v == -1 || removed[v as usize] || vals[u as usize] + vals[v as usize] != sum {
                continue;
            }

            let p = prev[u as usize];
            let nv = next[v as usize];
            ops += 1;

            // 1. 减去合并前涉及的逆序对
            if p != -1 && vals[p as usize] > vals[u as usize] {
                inv_count -= 1;
            }
            if vals[u as usize] > vals[v as usize] {
                inv_count -= 1;
            }
            if nv != -1 && vals[v as usize] > vals[nv as usize] {
                inv_count -= 1;
            }

            // 2. 执行合并
            vals[u as usize] = sum;
            next[u as usize] = nv;
            if nv != -1 {
                prev[nv as usize] = u;
            }
            removed[v as usize] = true;

            // 3. 加上合并后新增的逆序对
            if p != -1 && vals[p as usize] > vals[u as usize] {
                inv_count += 1;
            }
            if nv != -1 && vals[u as usize] > vals[nv as usize] {
                inv_count += 1;
            }

            // 4. 将新的相邻对推入堆
            if p != -1 {
                heap.push(Reverse((vals[p as usize] + vals[u as usize], p)));
            }
            if nv != -1 {
                heap.push(Reverse((vals[u as usize] + vals[nv as usize], u)));
            }
        }

        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.rs](sandbox:///mnt/agents/output/leetcode_3510.rs)