beautifulremi / 3507 and 3510. 移除最小数对使数组有序

Created Thu, 22 Jan 2026 16:30:38 +0800 Modified Mon, 23 Mar 2026 05:26:54 +0000
2078 Words
Leetcode

题目

给你一个数组 nums，你可以执行以下操作任意次数：

  • 选择 相邻 元素对中 和最小 的一对。如果存在多个这样的对，选择最左边的一个。
  • 用它们的和替换这对元素。

返回将数组变为 非递减 所需的 最小操作次数 。

如果一个数组中每个元素都大于或等于它前一个元素（如果存在的话），则称该数组为非递减。

示例 1：

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

输出： 2

解释：

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

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

示例 2：

输入： nums = [1,2,2]

输出： 0

解释：

数组 nums 已经是非递减的。

解题思路

这道题的本质是一个 “受限规则下的模拟题”。

我们需要解决三个核心难点：快速找最小、快速合并、高效判断结束条件。

难点一：怎么每次都快速找到“和最小”的那一对？

  • 暴力做法：每次遍历整个数组找最小值。时间复杂度 $O(N)$。如果有 $N$ 次操作，总耗时 $O(N^2)$，会超时。

  • 优化方案：使用 小顶堆 (Min-Heap) / 优先队列。

    • 堆顶永远是当前最小的和。

    • 取出最小值的时间是 $O(1)$，插入新值是 $O(\log N)$。

难点二：合并后，数组元素会移动，下标会乱，怎么办？

  • 暴力做法：使用数组 (ArrayList/List)。删除一个元素后，后面的元素都要向前挪位。时间复杂度 $O(N)$。

  • 优化方案：使用 双向链表 (Doubly Linked List)。

    • 不用真正的“移动”数据。

    • 只要改变指针：A <-> B <-> C，想删除 B，直接把 A 的 next 指向 C，C 的 prev 指向 A。时间复杂度 $O(1)$。

    • 最关键点：我们在堆里存的是 “节点的内存地址（引用）”，而不是数组下标。无论链表怎么变，节点对象本身在内存里是不动的，我们永远能找到它。

难点三：怎么知道数组已经“非递减”了？

  • 暴力做法：每次操作完，遍历链表检查一遍是否有序。时间复杂度 $O(N)$。

  • 优化方案：动态维护一个“逆序对计数器” (counter)。

    • 初始化时，统计有多少对相邻元素是 前 > 后 的，记为 cnt。

    • 每次合并操作只影响局部（左边那个、右边那个）。我们只检查这几个点，如果消除了逆序，cnt - 1；如果产生了新逆序，cnt + 1。

    • 当 cnt == 0 时，说明所有逆序都消失了，游戏结束。

我们需要封装一个链表节点类 Node：

class Node:
    def __init__(self, val, index):
        self.val = val       # 当前的值（会变大）
        self.index = index   # 初始下标（永远不变，仅用于堆中打破平局：谁index小谁在左边）
        self.prev = None     # 前驱指针
        self.next = None     # 后继指针
        self.removed = False # 标记：我是不是已经“死”了

同时我们要用到三个优化：

  1. 懒惰删除 (Lazy Deletion)：

    • 问题：当我们在 Round 1 把 Node2 删掉时，堆里还有一个 (7, 1, Node2) (即 2+5=7 这个数据)。如果专门去堆里找它并删掉，需要 $O(N)$，太慢。

    • 解决：不管它，让它留在堆里。等到有一天它浮到堆顶被 pop 出来时，我们看一眼 Node2.removed 是 True，直接丢弃 (continue)。这叫“懒惰删除”。

  2. 版本控制/过期检查：

    • 问题：Node3 的值从 3 变成了 5。堆里可能还存着它旧的“和”。

    • 解决：从堆里拿出 (sum, ...) 时，算一下 left.val + right.val 是否等于这个 sum。如果不相等，说明这是个过期数据，直接丢弃。

  3. 双向链表：

    • 保证了我们在合并节点时，不需要移动数组，只需要改指针，操作是 $O(1)$ 的。

复杂度分析

  • 时间复杂度：$O(N \log N)$

    • 每次合并操作，我们向堆里推入 1-2 个新元素。总共最多合并 $N$ 次。

    • 堆的操作是 $\log (\text{堆大小})$。

    • 所以总体是 $N \times \log N$。

  • 空间复杂度：$O(N)$

    • 链表节点 $N$ 个。

    • 堆中最多存 $O(N)$ 个数据（包括那些还没来得及清理的脏数据）。

具体代码

import heapq
from typing import List

class Node:
    def __init__(self, val, index):
        self.val = val
        self.index = index  # 这里的 index 仅用于堆中打破平局（最左优先），初始化后不再改变
        self.prev = None
        self.next = None
        self.removed = False # 标记节点是否被删除

class Solution:
    def minimumPairRemoval(self, nums: List[int]) -> int:
        n = len(nums)
        if n < 2:
            return 0
        
        # 1. 构建双向链表
        nodes = [Node(x, i) for i, x in enumerate(nums)]
        for i in range(n):
            if i > 0:
                nodes[i].prev = nodes[i - 1]
            if i < n - 1:
                nodes[i].next = nodes[i + 1]
        
        # 2. 初始化堆和逆序对计数
        # 堆中存储元组: (相邻和, 左节点索引, 左节点对象)
        # Python的元组比较是逐个比较的，这自然满足了题目要求：
        # 先比和(sum)，和一样比索引(index)小的（即最左边）
        heap = []
        unsorted_count = 0
        
        # 辅助函数：判断当前节点和它的下一个节点是否构成逆序（非递减破坏者）
        def is_inversion(node):
            if node and node.next and node.val > node.next.val:
                return 1
            return 0
        
        for i in range(n - 1):
            # 将所有相邻对加入堆
            heapq.heappush(heap, (nodes[i].val + nodes[i+1].val, nodes[i].index, nodes[i]))
            # 统计初始逆序对
            unsorted_count += is_inversion(nodes[i])
            
        ops = 0
        
        # 3. 模拟循环
        while unsorted_count > 0:
            # --- 从堆中取出有效的最小对 ---
            valid_pair_found = False
            left_node = None
            right_node = None
            
            while heap:
                current_sum, _, left_node = heapq.heappop(heap)
                
                # 检查有效性 (Lazy Deletion Check):
                # 1. 左节点必须没被删除
                # 2. 左节点必须还有下一个节点 (可能已经是尾节点了)
                # 3. 下一个节点也没被删除
                if left_node.removed or left_node.next is None or left_node.next.removed:
                    continue
                
                right_node = left_node.next
                
                # 4. 关键检查：因为 left_node 的值可能在之前的合并中变大了，
                # 导致堆里存的这个 current_sum 是旧数据（过期数据）。
                if left_node.val + right_node.val != current_sum:
                    continue
                
                # 找到了有效且最新的最小对
                valid_pair_found = True
                break
            
            # --- 准备合并 ---
            prev_node = left_node.prev
            next_next_node = right_node.next # 右节点的右边
            
            # --- 更新逆序计数 (减去旧关系的贡献) ---
            # 涉及的关系有： (prev, left), (left, right), (right, next_next)
            if prev_node:
                unsorted_count -= is_inversion(prev_node)
            unsorted_count -= is_inversion(left_node)
            unsorted_count -= is_inversion(right_node)
            
            # --- 执行合并操作 ---
            # 更新左节点的值
            left_node.val += right_node.val
            # 标记右节点为删除
            right_node.removed = True
            # 调整指针，将右节点从链中断开
            left_node.next = next_next_node
            if next_next_node:
                next_next_node.prev = left_node
            
            # --- 更新逆序计数 (加上新关系的贡献) ---
            # 新的关系只有： (prev, left_new), (left_new, next_next)
            if prev_node:
                unsorted_count += is_inversion(prev_node)
            unsorted_count += is_inversion(left_node)
            
            # --- 将产生的新相邻对加入堆 ---
            # 1. 左边的新对: prev + left
            if prev_node:
                new_sum_left = prev_node.val + left_node.val
                heapq.heappush(heap, (new_sum_left, prev_node.index, prev_node))
            
            # 2. 右边的新对: left + next_next
            if next_next_node:
                new_sum_right = left_node.val + next_next_node.val
                heapq.heappush(heap, (new_sum_right, left_node.index, left_node))
                
            ops += 1
            
        return ops