以下是 LeetCode 3510. Minimum Pair Removal to Sort Array II 的 Python3 实现。解题思路这道题要求将时间复杂度从 O(n²) 优化到 O(n log n)核心思路是1. 最小相邻对查找使用 最小堆 (heapq) 维护所有相邻元素对的和支持 O(log n) 的插入和弹出最小值。2. 有序性判断不每次扫描整个数组而是维护一个 num_descending 计数器记录当前有多少对相邻元素是递减的即 nums[i] nums[i1]。当计数器为 0 时数组即为非递减序列。3. 双向链表使用 Node 类模拟双向链表实现 O(1) 的节点删除操作。合并两个节点时只需修改指针无需实际移动数组元素。4. 惰性删除堆中可能包含过期的相邻对信息因为某些节点已被合并弹出时检查 node.value node.next.value value不匹配则跳过。Python3 代码pythonimport heapqfrom typing import Listclass Node:def __init__(self, value: int, i: int):self.value value # 当前节点的值self.i i # 原始下标用于打破平局选最左边的对self.prev None # 前一个节点self.next None # 后一个节点self.descending False # 当前节点值 下一个节点值def remove(self):从双向链表中移除当前节点if self.prev:self.prev.next self.nextif self.next:self.next.prev self.prevself.next self.prev Noneclass Solution:def minimumPairRemoval(self, nums: List[int]) - int:n len(nums)if n 1:return 0# 初始化双向链表从右往左构建tail Node(nums[-1], n - 1)for i in range(n - 2, -1, -1):head Node(nums[i], i)head.next tailtail.prev headtail head# 初始化最小堆存储 (相邻对和, 左端点原始下标, 左端点节点引用)heap []num_descending 0cur tailwhile cur and cur.next:heap.append((cur.value cur.next.value, cur.i, cur))cur.descending cur.value cur.next.valueif cur.descending:num_descending 1cur cur.nextif num_descending 0:return 0heapq.heapify(heap)num_operations 0while num_descending 0:value, _, node heapq.heappop(heap)# 惰性删除检查这对是否仍然有效# 如果 node 已被合并没有 next或者和已改变则跳过if not node.next or node.value node.next.value ! value:continue# 合并 node 和 node.next# 1. 处理 node.next 的 descending 标记if node.next.descending:num_descending - 1# 2. 移除 node.next 节点node.next.remove()# 3. 更新 node 的值为两数之和node.value valuenum_operations 1# 4. 更新与 node 相关的相邻对前一个和当前节点for pair in (node.prev, node):if not pair:continuedescending Falseif pair.next:# 将新的相邻对和推入堆heapq.heappush(heap, (pair.value pair.next.value, pair.i, pair))descending pair.value pair.next.value# 更新 descending 计数num_descending descending - pair.descendingpair.descending descendingreturn num_operations复杂度分析- 时间复杂度O(n log n)。每次堆操作 O(log n)每个节点最多被合并一次每个相邻对最多被推入堆两次。- 空间复杂度O(n)。用于存储链表节点和堆。
