题目信息

  • 平台：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
'''

class Solution:
    def minimumPairRemoval(self, nums: List[int]) -> int:
        cnt = 0

        while len(nums)>1:
            isAscending = True
            minSum = inf
            target_idx = -1

            for i in range(len(nums)-1):
                pair_sum = nums[i]+nums[i+1]
                if nums[i]>nums[i+1]:
                    isAscending = False

                if minSum > pair_sum:
                    minSum = pair_sum
                    target_idx = i
                
            if isAscending:
                break

            cnt += 1
            nums[target_idx] = minSum
            nums.pop(target_idx+1)
        return cnt

总结与反思

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