2026-01-22-LeetCode刷题笔记-3507-移除最小数对使数组有序I

title: 2026-01-22-LeetCode刷题笔记-3507-移除最小数对使数组有序I
date: 2026-01-22
tags:

• 算法学习
• LeetCode
• 贪心

题目信息

• 平台：LeetCode
• 题目：3507. 移除最小数对使数组有序 I
• 难度：简单
• 题目链接

题目描述

给定数组 nums，每次可以选择相邻的一对元素，将它们合并为它们的和（等价于删除这对并用和替代）。每次操作选择“当前相邻对和最小”的那一对。问最少需要多少次操作，才能让数组变为非递减序列。

初步思路

1. 只要数组已非递减，就停止。
2. 否则在当前数组里遍历所有相邻对，找到和最小的一对进行合并。
3. 重复上述过程，统计操作次数。

算法分析

• 核心：每轮扫描所有相邻对，若仍无序则合并最小对
• 技巧：一次遍历同时判断是否已非递减，并找到最小相邻对
• 时间复杂度：O(k·n)，k 为合并次数（每次遍历当前数组）
• 空间复杂度：O(1)（原地修改列表）

代码实现（Python）

''' Author: tkzzzzzz6 Date: 2026-01-22 22:28:44 LastEditors: tkzzzzzz6 LastEditTime: 2026-01-22 22:47:28 '''classSolution:defminimumPairRemoval(self,nums:List[int])->int:cnt=0whilelen(nums)>1:isAscending=TrueminSum=inf target_idx=-1foriinrange(len(nums)-1):pair_sum=nums[i]+nums[i+1]ifnums[i]>nums[i+1]:isAscending=FalseifminSum>pair_sum:minSum=pair_sum target_idx=iifisAscending:breakcnt+=1nums[target_idx]=minSum nums.pop(target_idx+1)returncnt

总结与反思

1. 每轮遍历既能判断是否有序，也能确定最小相邻对。
2. 该实现为直接模拟，便于理解，但在数据规模大时会偏慢。