2025-09-29：移除最小数对使数组有序Ⅰ。用go语言，给定一个整数数组 nums，可以重复进行一种合并操作：每次在所有相邻

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)
}

# -*-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)  # 输出结果