优化LeetCode 3510题Minimum Pair Removal to Sort Array II解法以规避超时

原代码的性能瓶颈 #

你的代码逻辑正确，但处理大规模输入时超时，核心原因是**O(n²)**的时间复杂度：

• 每次循环全量检查数组是否有序，单次O(n)，多次循环累计O(n²)
• 每次遍历所有相邻对找最小和，单次O(n)，累计O(n²)
• 列表的insert和del操作是O(n)级别的，需要移动大量元素，多次操作后耗时剧增

优化思路（不改变核心逻辑） #

要保留「每次选择最左的最小和相邻配对合并」的核心逻辑并优化，需解决三个关键问题：

1. 高效判断数组是否有序：维护相邻逆序对的计数，当计数为0时数组非递减，无需全量遍历
2. 高效查找最小和配对：用优先队列（堆）维护所有有效相邻对，结合懒惰删除避免无效操作，单次查找O(log n)
3. 高效执行合并操作：用双向链表替代列表，合并相邻节点仅需修改指针，O(1)时间完成

优化后的代码 #

import heapq
from typing import List

class Node:
    __slots__ = ['val', 'prev', 'next', 'valid']  # 减少内存开销，提升速度
    def __init__(self, val):
        self.val = val
        self.prev = None
        self.next = None
        self.valid = True  # 标记节点是否未被合并

class Solution:
    def minimumPairRemoval(self, nums: List[int]) -> int:
        n = len(nums)
        if n <= 1:
            return 0
        
        # 初始化双向链表
        nodes = [Node(num) for num in nums]
        for i in range(n-1):
            nodes[i].next = nodes[i+1]
            nodes[i+1].prev = nodes[i]
        
        # 统计初始相邻逆序对数量
        reverse_count = 0
        for i in range(n-1):
            if nodes[i].val > nodes[i+1].val:
                reverse_count += 1
        if reverse_count == 0:
            return 0
        
        # 初始化堆：存储(相邻和, 左节点)，堆顶是最小和的配对
        heap = []
        for i in range(n-1):
            heapq.heappush(heap, (nodes[i].val + nodes[i+1].val, nodes[i]))
        
        op = 0
        while reverse_count > 0:
            # 弹出有效最小和配对（懒惰删除无效项）
            while heap:
                current_sum, left_node = heapq.heappop(heap)
                # 检查配对是否有效：左节点存在，右节点存在且都未被合并
                if left_node.valid and left_node.next and left_node.next.valid:
                    right_node = left_node.next
                    break
            else:
                break  # 理论上不会走到这里，因为reverse_count>0时必有可合并项
            
            # 计算合并前需要减去的逆序对
            # 左节点与前一个节点的逆序对
            if left_node.prev:
                if left_node.prev.val > left_node.val:
                    reverse_count -= 1
            # 左节点与右节点的逆序对
            if left_node.val > right_node.val:
                reverse_count -= 1
            # 右节点与后一个节点的逆序对
            if right_node.next:
                if right_node.val > right_node.next.val:
                    reverse_count -= 1
            
            # 合并两个节点，创建新节点
            merged_val = left_node.val + right_node.val
            merged_node = Node(merged_val)
            
            # 修改链表指针
            merged_node.prev = left_node.prev
            merged_node.next = right_node.next
            if left_node.prev:
                left_node.prev.next = merged_node
            if right_node.next:
                right_node.next.prev = merged_node
            
            # 标记原节点为无效
            left_node.valid = False
            right_node.valid = False
            
            # 计算合并后新增的逆序对
            if merged_node.prev:
                if merged_node.prev.val > merged_node.val:
                    reverse_count += 1
                # 将新的相邻对（前节点与合并节点）加入堆
                heapq.heappush(heap, (merged_node.prev.val + merged_node.val, merged_node.prev))
            if merged_node.next:
                if merged_node.val > merged_node.next.val:
                    reverse_count += 1
                # 将新的相邻对（合并节点与后节点）加入堆
                heapq.heappush(heap, (merged_node.val + merged_node.next.val, merged_node))
            
            op += 1
        
        return op

优化说明 #

1. 双向链表：通过Node类实现，合并操作仅需修改前后指针，避免了列表的O(n)移动开销
2. 优先队列+懒惰删除：堆中存储所有相邻对的和与左节点，弹出时检查节点有效性，跳过已合并的无效配对，确保每次弹出的是当前有效的最小和配对
3. 逆序对计数：维护reverse_count变量，仅在合并前后修改受影响的相邻逆序对数量，无需全量遍历数组判断有序性，大幅减少重复计算

内容的提问来源于stack exchange，提问作者manhera