Kimi LeetCode 3510. 移除最小数对使数组有序 II Python3实现
以下是 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[i+1]`）。当计数器为 0 时，数组即为非递减序列。
3. 双向链表：使用 `Node` 类模拟双向链表，实现 O(1) 的节点"删除"操作。合并两个节点时，只需修改指针，无需实际移动数组元素。
4. 惰性删除：堆中可能包含过期的相邻对信息（因为某些节点已被合并），弹出时检查 `node.value + node.next.value == value`，不匹配则跳过。
Python3 代码
```python
import heapq
from typing import List
class 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.next
if self.next:
self.next.prev = self.prev
self.next = self.prev = None
class 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 = tail
tail.prev = head
tail = head
# 初始化最小堆，存储 (相邻对和, 左端点原始下标, 左端点节点引用)
heap = []
num_descending = 0
cur = tail
while cur and cur.next:
heap.append((cur.value + cur.next.value, cur.i, cur))
cur.descending = cur.value > cur.next.value
if cur.descending:
num_descending += 1
cur = cur.next
if num_descending == 0:
return 0
heapq.heapify(heap)
num_operations = 0
while 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 = value
num_operations += 1
# 4. 更新与 node 相关的相邻对（前一个和当前节点）
for pair in (node.prev, node):
if not pair:
continue
descending = False
if pair.next:
# 将新的相邻对和推入堆
heapq.heappush(heap, (pair.value + pair.next.value, pair.i, pair))
descending = pair.value > pair.next.value
# 更新 descending 计数
num_descending += descending - pair.descending
pair.descending = descending
return num_operations
```
复杂度分析
- 时间复杂度：O(n log n)。每次堆操作 O(log n)，每个节点最多被合并一次，每个相邻对最多被推入堆两次。
- 空间复杂度：O(n)。用于存储链表节点和堆。