2025-09-29：移除最小数对使数组有序Ⅰ。用go语言，给定一个整数数组 nums，可以重复进行一种合并操作：每次在所有相邻的两个元素中选出它们之和最小的一对（若有多个并列，取最靠左的那个），把这两个元素用它们的和替换成一个数。

问要把数组变成从左到右不下降（即每个元素不小于前一个）的状态，至少需要多少次这样的合并操作，返回该最小次数。

1 <= nums.length <= 50。

-1000 <= nums[i] <= 1000。

输入： nums = [5,2,3,1]。

输出： 2。

解释：

元素对 (3,1) 的和最小，为 4。替换后 nums = [5,2,4]。

元素对 (2,4) 的和为 6。替换后 nums = [5,6]。

数组 nums 在两次操作后变为非递减。

题目来自力扣3507。

分步骤描述

1. 初始化阶段

• 计算初始逆序对：遍历数组，统计相邻元素中前面大于后面的情况（即递减对的数量 dec）。
• 构建最小堆：创建一个最小堆，存储所有相邻元素对的和以及左边元素的索引。堆按照和的大小排序（和相同则按索引从左到右）。
• 维护双向链表：创建 left 和 right 数组，模拟双向链表结构，用于快速找到每个元素左右相邻的未删除元素。

2. 循环处理阶段（当存在递减对时）

每次循环代表一次合并操作：

1. 选择最小和的对：

   • 从堆顶取出当前和最小的相邻对。
   • 由于数组在变化，需要验证堆顶元素是否仍然有效（对应位置的元素未被删除且和未改变）。
   • 如果无效则弹出，继续检查下一个，直到找到有效的。

2. 执行合并操作：

   • 将选中的两个相邻元素替换为它们的和。
   • 更新数组：将左边元素的值改为两数之和，右边元素标记为已删除。

3. 更新递减对计数：

   • 移除旧影响：合并前，检查被合并的对本身是否是一个递减对，如果是则 dec--。同时检查被合并元素与它左右相邻元素形成的递减对，这些旧关系也会消失。
   • 添加新影响：合并后，新产生的值与它左右相邻元素可能形成新的递减对，需要相应增加 dec。

4. 更新堆和链表：

   • 更新堆：将新形成的相邻对（新值与左边元素、新值与右边元素）的和及索引加入堆中。
   • 更新链表：通过 remove 函数从双向链表中删除被合并的右边元素，维护剩余元素的相邻关系。

3. 终止条件

当递减对数量 dec 变为 0，即数组中不再存在前面元素大于后面元素的情况时，循环结束。此时数组已变为非递减序列。

复杂度分析

时间复杂度

• 最坏情况下需要合并 n-1 次（每次减少一个元素）。
• 每次操作中，堆操作（Push/Pop）是 O(log n)，更新计数和链表是 O(1)。
• 总时间复杂度：O(n log n)。

额外空间复杂度

• 堆空间：O(n)
• 左右链表数组：O(n)
• 其他变量：O(1)
• 总额外空间复杂度：O(n)。

Go完整代码如下：

package main

import (
	"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 < n {
			if nums[nxt] > 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 []pair

func (h hp) Len() int           { return len(h) }
func (h hp) Less(i, j int) bool { a, b := h[i], h[j]; return a.s < b.s || a.s == b.s && a.i < b.i }
func (h hp) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v any)        { *h = append(*h, v.(pair)) }
func (h *hp) Pop() any          { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }

func main() {
	nums := []int{5, 2, 3, 1}
	result := minimumPairRemoval(nums)
	fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

import heapq

def minimumPairRemoval(nums):
    n = len(nums)
    if n <= 1:
        return 0
    
    # 创建最小堆，存储(相邻元素和, 左边元素索引)
    heap = []
    # 统计递减对的个数
    dec = 0
    
    # 初始化堆和递减对计数
    for i in range(n - 1):
        x, y = nums[i], nums[i + 1]
        if x > y:
            dec += 1
        heapq.heappush(heap, (x + y, i))
    
    # 每个下标的左右最近的未删除下标
    left = [i - 1 for i in range(n + 1)]  # 加一个哨兵，防止下标越界
    right = [i + 1 for i in range(n)]
    removed = [False] * n  # 标记元素是否被删除
    
    ans = 0
    
    while dec > 0:
        ans += 1
        
        # 找到第一个有效的堆顶元素
        while heap:
            s, i = heap[0]
            # 检查这个元素对是否仍然有效
            if (removed[i] or removed[right[i]] or 
                nums[i] + nums[right[i]] != s):
                heapq.heappop(heap)
            else:
                break
        
        if not heap:
            break
            
        # 删除相邻元素和最小的一对
        s, i = heapq.heappop(heap)
        nxt = right[i]
        
        # 检查旧递减对
        if nums[i] > nums[nxt]:  # 旧数据
            dec -= 1
        
        # 处理前一个元素
        pre = left[i]
        if pre >= 0 and not removed[pre]:
            # 检查旧递减对
            if nums[pre] > nums[i]:  # 旧数据
                dec -= 1
            # 检查新递减对
            if nums[pre] > s:  # 新数据
                dec += 1
            heapq.heappush(heap, (nums[pre] + s, pre))
        
        # 处理后一个元素的下一个元素
        nxt2 = right[nxt]
        if nxt2 < n and not removed[nxt2]:
            # 检查旧递减对
            if nums[nxt] > nums[nxt2]:  # 旧数据
                dec -= 1
            # 检查新递减对
            if s > nums[nxt2]:  # 新数据
                dec += 1
            heapq.heappush(heap, (s + nums[nxt2], i))
        
        # 更新当前元素的值
        nums[i] = s
        
        # 标记删除下一个元素
        removed[nxt] = True
        
        # 更新左右指针
        right[i] = nxt2
        if nxt2 < n:
            left[nxt2] = i
    
    return ans

# 测试代码
if __name__ == "__main__":
    nums = [5, 2, 3, 1]
    result = minimumPairRemoval(nums)
    print(result)  # 输出结果