3510. 移除最小数对使数组有序 II —— 详细技术解析目录1. 题目描述2. 示例分析3. 解题思路概述4. 暴力模拟解法5. 优化解法双向链表 最小堆 懒惰删除5.1 核心思想5.2 数据结构设计5.3 逆序对的维护5.4 报错问题修复详解5.5 算法流程图5.6 复杂度分析5.7 最终可AC代码带完整注释6. 其他思路线段树 / 平衡树7. 易错点与总结1. 题目描述给你一个数组nums你可以执行以下操作任意次数选择相邻元素对中和最小的一对。如果存在多个这样的对选择最左边的一个。用它们的和替换这对元素。返回将数组变为非递减所需的最小操作次数。非递减数组每个元素都大于或等于它前一个元素如果存在的话。提示1 \lt; nums\.length \lt; 10^5\-10^9 \lt; nums\[i\] \lt; 10^92. 示例分析示例 1输入nums [5,2,3,1] 输出2 解释 1. 相邻对 (3,1) 和最小为4。替换后 nums [5,2,4] 2. 相邻对 (2,4) 和为6。替换后 nums [5,6] 此时数组非递减共操作2次。示例 2输入nums [1,2,2] 输出0 解释数组已经非递减不需要操作。3. 解题思路概述核心操作是“每次挑最小和的相邻对合并”操作逻辑类似哈夫曼树构建过程但合并位置严格受数组相邻顺序限制无法自由选择节点合并。题目数据规模最大为10^5暴力每次遍历数组查找最小对的O\(n²\)算法会直接超时因此必须使用高效数据结构优化快速获取全局最小和相邻对且满足和相同时选取最左侧的规则动态更新合并后的数组结构快速维护相邻关系实时判断数组有序状态避免每次全局遍历校验。主流最优解法为双向链表 最小堆 懒惰删除此外还有线段树、平衡树等进阶思路。下文先讲解暴力解法帮助理解题意再重点讲解可AC的最优解法。4. 暴力模拟解法解题思路全程模拟题目操作规则循环遍历数组每次查找和最小的最左相邻对合并元素直到数组变为非递减。该方法逻辑简单、完全贴合题意适合新手理解题目逻辑但时间复杂度过高无法通过大数据用例。代码实现from typing import List class Solution: def minimumPairRemoval(self, nums: List[int]) - int: # 判断数组是否为非递减 def is_non_decreasing(arr): for i in range(len(arr) - 1): if arr[i] arr[i 1]: return False return True ans 0 arr nums[:] # 循环操作直到数组有序 while not is_non_decreasing(arr): min_sum float(inf) target_idx -1 # 遍历所有相邻对找最小和、最左侧的一对 for i in range(len(arr) - 1): cur_sum arr[i] arr[i 1] if cur_sum min_sum: min_sum cur_sum target_idx i # 合并相邻对 new_val arr[target_idx] arr[target_idx 1] arr arr[:target_idx] [new_val] arr[target_idx 2:] ans 1 return ans复杂度分析时间复杂度O\(n²\)最多合并n\-1次每次合并需要遍历数组查找最小对、校验数组有序性空间复杂度O\(n\)拷贝数组存储操作后的结果。5. 优化解法双向链表 最小堆 懒惰删除5.1 核心思想针对暴力解法的超时问题通过三种数据结构组合优化将时间复杂度降至O\(n log n\)适配10^5数据规模双向链表替代普通数组实现O\(1\)时间的节点删除、插入、相邻节点查询解决数组修改低效问题最小堆预存所有相邻元素对的和、位置信息每次直接弹出全局最小和对无需遍历数组懒惰删除合并操作会让堆中旧的元素对失效不主动清理堆仅在弹出时校验有效性大幅减少操作开销逆序对计数实时维护数组中相邻逆序对的数量计数为0即代表数组完全有序无需全局校验。5.2 数据结构设计自定义链表节点每个节点存储数值、前后指针、删除标记、最左原始下标使用\_\_slots\_\_优化内存占用适配大数据量val当前节点存储的数值合并后的累加和prev/next双向链表前后指针deleted节点失效标记用于懒惰删除校验leftmost\_index节点对应原始数组的最左下标用于实现「和相同选最左」的规则。堆存储规则堆中存储三元组\(pair\_sum, leftmost\_index, left\_node\)Python堆自动按元组顺序排序优先比较和和相同则比较最左下标天然满足题目选最左的规则。5.3 逆序对的维护逆序对数量inv是判断数组是否有序的核心依据每次合并操作需要先删旧逆序对、再加新逆序对保证计数准确删除旧逆序对合并两个节点前消除这两个节点与前后节点形成的所有逆序对合并生成新节点替换原有两个节点新增新逆序对统计新节点与前后节点形成的逆序对更新计数。5.4 报错问题修复详解报错原因原始代码运行会抛出TypeError: \\#39;\lt;\\#39; not supported between instances of \\#39;Node\\#39; and \\#39;Node\\#39;。原因是当堆中两个元素的pair\_sum和leftmost\_index完全相同时Python会尝试比较三元组第三个元素Node对象而自定义节点类未实现大小比较方法导致报错。修复方案为Node类新增\_\_lt\_\_方法基于leftmost\_index实现节点大小比较既解决报错又完全贴合题目排序规则保证堆排序逻辑正确。5.5 算法流程图初始化构建双向链表统计初始逆序对数量若为0直接返回0将所有初始相邻元素对压入最小堆循环处理只要存在逆序对就弹出堆中有效最小和相邻对更新逆序对计数合并节点、更新链表结构、标记旧节点失效将新生成的相邻对压入堆累计操作次数逆序对清零后返回操作次数。5.6 复杂度分析时间复杂度O\(n log n\)最多合并n\-1次每次堆弹出、压入操作均为O\(log n\)链表操作为常数级空间复杂度O\(n\)链表节点、堆存储均为线性空间。5.7 最终可AC代码带完整注释from typing import List import heapq class Node: # 优化内存占用固定对象属性 __slots__ (val, prev, next, deleted, leftmost_index) def __init__(self, val: int, leftmost_index: int): self.val val self.prev None self.next None self.deleted False self.leftmost_index leftmost_index # 修复Node对象无法比较的报错基于最左下标排序 def __lt__(self, other): return self.leftmost_index other.leftmost_index class Solution: def minimumPairRemoval(self, nums: List[int]) - int: n len(nums) # 长度小于2天然非递减无需操作 if n 1: return 0 # 1. 构建双向链表 nodes [Node(nums[i], i) for i in range(n)] for i in range(n - 1): nodes[i].next nodes[i 1] nodes[i 1].prev nodes[i] # 2. 统计初始相邻逆序对数量 inv 0 for i in range(n - 1): if nums[i] nums[i 1]: inv 1 # 无逆序对直接返回0 if inv 0: return 0 # 3. 初始化最小堆存入所有相邻元素对 heap [] for i in range(n - 1): left nodes[i] right nodes[i 1] pair_sum left.val right.val # 堆元组(和, 最左下标, 左节点) heapq.heappush(heap, (pair_sum, left.leftmost_index, left)) ans 0 # 4. 循环合并直到数组完全有序无逆序对 while inv 0: # 懒惰删除过滤堆中失效的元素对 while heap: s, idx, left_node heapq.heappop(heap) # 节点已被删除跳过 if left_node.deleted: continue right_node left_node.next # 右节点不存在或已删除跳过 if right_node is None or right_node.deleted: continue # 当前节点和与堆中存储和不一致说明失效跳过 if left_node.val right_node.val ! s: continue # 找到有效最小和对 break # 4.1 移除旧的逆序对合并前清理原有相邻关系 # 清理左节点前驱与左节点的逆序 if left_node.prev: if left_node.prev.val left_node.val: inv - 1 # 清理当前合并对的逆序 if left_node.val right_node.val: inv - 1 # 清理右节点后继与右节点的逆序 if right_node.next: if right_node.val right_node.next.val: inv - 1 # 4.2 合并两个节点生成新节点 new_val left_node.val right_node.val # 新节点继承左节点的最左下标保证排序规则正确 new_node Node(new_val, left_node.leftmost_index) new_node.prev left_node.prev new_node.next right_node.next # 更新前后节点的指向 if left_node.prev: left_node.prev.next new_node if right_node.next: right_node.next.prev new_node # 标记旧节点失效 left_node.deleted True right_node.deleted True # 4.3 添加新的逆序对并将新相邻对入堆 if new_node.prev: # 新增前驱与新节点的逆序关系 if new_node.prev.val new_node.val: inv 1 # 新相邻对入堆 heapq.heappush( heap, (new_node.prev.val new_node.val, new_node.prev.leftmost_index, new_node.prev) ) if new_node.next: # 新增新节点与后继的逆序关系 if new_node.val new_node.next.val: inv 1 # 新相邻对入堆 heapq.heappush( heap, (new_node.val new_node.next.val, new_node.leftmost_index, new_node) ) # 累计操作次数 ans 1 return ans6. 其他思路线段树 / 平衡树线段树解法思路可以通过线段树维护所有相邻元素对的\(和, 最左下标\)信息线段树叶子节点存储单个相邻对信息父节点维护区间内的最小和、最左位置初始化线段树录入所有相邻对数据每次查询线段树根节点快速获取全局最小和相邻对合并节点后删除原有两个相邻对更新新增的两个相邻对完成线段树单点更新同步维护逆序对计数直至数组有序。该解法时间复杂度同样为O\(n log n\)但代码量极大、逻辑复杂容错率低在Python中性价比远低于堆链表解法。平衡树解法思路借助有序平衡树存储有效相邻对支持快速查询最小值、动态删除/插入元素。但Python无内置平衡树第三方库在LeetCode无法使用仅作为竞赛拓展思路。7. 易错点与总结核心易错点堆排序报错问题必须为Node类实现\_\_lt\_\_方法否则等值情况下会触发对象比较报错懒惰删除校验不全必须同时校验节点删除状态、相邻关系有效性、和值一致性否则会处理失效节点导致答案错误逆序对计数顺序错误必须先删除旧逆序对再新增新逆序对顺序颠倒会导致计数错乱引发死循环或提前退出最左规则失效新节点必须继承左节点的leftmost\_index保证和相同时优先选择左侧节点边界漏判需单独处理数组长度≤1、初始已有序的特殊用例。算法总结本题的核心是贪心策略 高效数据结构模拟题目固定了贪心规则每次合并最小和最左相邻对解题关键不再是推导贪心正确性而是用最优的数据结构高效模拟合并过程。双向链表 最小堆 懒惰删除是Python环境下本题的最优解兼顾代码简洁性、时间效率和稳定性可完美通过全部10^5大数据用例。