摘要：2025-09-29：移除最小数对使数组有序Ⅰ。用go语言，给定一个整数数组 nums，可以重复进行一种合并操作：每次在所有相邻的两个元素中选出它们之和最小的一对（若有多个并列，取最靠左的那个），把这两个元素用它们的和替换成一个数。
2025-09-29：移除最小数对使数组有序Ⅰ。用go语言，给定一个整数数组 nums，可以重复进行一种合并操作：每次在所有相邻的两个元素中选出它们之和最小的一对（若有多个并列，取最靠左的那个），把这两个元素用它们的和替换成一个数。
问要把数组变成从左到右不下降（即每个元素不小于前一个）的状态，至少需要多少次这样的合并操作，返回该最小次数。
1
-1000
输入： nums = [5,2,3,1]。
输出： 2。
解释：
元素对 (3,1) 的和最小，为 4。替换后 nums = [5,2,4]。
元素对 (2,4) 的和为 6。替换后 nums = [5,6]。
数组 nums 在两次操作后变为非递减。
题目来自力扣3507。
• 计算初始逆序对：遍历数组，统计相邻元素中前面大于后面的情况（即递减对的数量 dec）。
• 构建最小堆：创建一个最小堆，存储所有相邻元素对的和以及左边元素的索引。堆按照和的大小排序（和相同则按索引从左到右）。
• 维护双向链表：创建 left 和 right 数组，模拟双向链表结构，用于快速找到每个元素左右相邻的未删除元素。
每次循环代表一次合并操作：
1. 选择最小和的对：
• 从堆顶取出当前和最小的相邻对。
• 由于数组在变化，需要验证堆顶元素是否仍然有效（对应位置的元素未被删除且和未改变）。
• 如果无效则弹出，继续检查下一个，直到找到有效的。
2. 执行合并操作：
• 将选中的两个相邻元素替换为它们的和。
• 更新数组：将左边元素的值改为两数之和，右边元素标记为已删除。
3. 更新递减对计数：
• 移除旧影响：合并前，检查被合并的对本身是否是一个递减对，如果是则 dec--。同时检查被合并元素与它左右相邻元素形成的递减对，这些旧关系也会消失。
• 添加新影响：合并后，新产生的值与它左右相邻元素可能形成新的递减对，需要相应增加 dec。
4. 更新堆和链表：
• 更新堆：将新形成的相邻对（新值与左边元素、新值与右边元素）的和及索引加入堆中。
• 更新链表：通过 remove 函数从双向链表中删除被合并的右边元素，维护剩余元素的相邻关系。
当递减对数量 dec 变为 0，即数组中不再存在前面元素大于后面元素的情况时，循环结束。此时数组已变为非递减序列。
• 最坏情况下需要合并 n-1 次（每次减少一个元素）。
• 每次操作中，堆操作（Push/Pop）是 O(log n)，更新计数和链表是 O(1)。
• 总时间复杂度：O(n log n)。
• 堆空间：O(n)
• 左右链表数组：O(n)
• 其他变量：O(1)
• 总额外空间复杂度：O(n)。
package mainimport ( "container/heap" "fmt")func minimumPairRemoval(nums int) (ans int) { n := len(nums) h := make(hp, n-1) dec := 0 // 递减的相邻对的个数 for i := range n - 1 { x, y := nums[i], nums[i+1] if x > y { dec++ } h[i] = pair{x + y, i} } heap.Init(&h) // 每个下标的左右最近的未删除下标 left := make(int, n+1) // 加一个哨兵，防止下标越界 right := make(int, n) for i := range n { left[i] = i - 1 right[i] = i + 1 } remove := func(i int) { l, r := left[i], right[i] right[l] = r // 模拟双向链表的删除操作 left[r] = l right[i] = n // 表示 i 已被删除 } for dec > 0 { ans++ for right[h[0].i] >= n || nums[h[0].i]+nums[right[h[0].i]] != h[0].s { heap.Pop(&h) } p := heap.Pop(&h).(pair) // 删除相邻元素和最小的一对 s := p.s i := p.i // (当前元素，下一个数) nxt := right[i] if nums[i] > nums[nxt] { // 旧数据 dec-- } // (前一个数，当前元素) pre := left[i] if pre >= 0 { if nums[pre] > nums[i] { // 旧数据 dec-- } if nums[pre] > s { // 新数据 dec++ } heap.Push(&h, pair{nums[pre] + s, pre}) } // (下一个数，下下一个数) nxt2 := right[nxt] if nxt2 nums[nxt2] { // 旧数据 dec-- } if s > nums[nxt2] { // 新数据（当前元素，下下一个数） dec++ } heap.Push(&h, pair{s + nums[nxt2], i}) } nums[i] = s remove(nxt) } return}type pair struct{ s, i int } // (相邻元素和，左边那个数的下标)type hp pairfunc (h hp) Len int { return len(h) }func (h hp) Less(i, j int) bool { a, b := h[i], h[j]; return a.s我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。
来源：菲尔顺教育
