LeetCode 题解工作台
移除最小数对使数组有序 I
给你一个数组 nums ，你可以执行以下操作任意次数： 选择 相邻 元素对中 和最小 的一对。如果存在多个这样的对，选择最左边的一个。 用它们的和替换这对元素。 返回将数组变为 非递减 所需的 最小操作次数 。 如果一个数组中每个元素都大于或等于它前一个元素（如果存在的话），则称该数组为 非递减 。…
7
题型
6
代码语言
3
相关题
当前训练重点
简单 · 数组·哈希·扫描
答案摘要
我们定义一个函数 ，用于判断数组 是否为非递减数组。 我们使用一个循环，直到数组 为非递减数组为止。在每次循环中，我们找到数组 中相邻元素对的和的最小值，并记录该对的左边元素的下标 。然后，我们将该对的和替换左边的元素，并删除右边的元素。最后，我们返回操作的次数。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个数组 nums，你可以执行以下操作任意次数：
- 选择 相邻 元素对中 和最小 的一对。如果存在多个这样的对，选择最左边的一个。
- 用它们的和替换这对元素。
返回将数组变为 非递减 所需的 最小操作次数 。
如果一个数组中每个元素都大于或等于它前一个元素（如果存在的话），则称该数组为非递减。
示例 1：
输入： nums = [5,2,3,1]
输出： 2
解释：
- 元素对
(3,1)的和最小，为 4。替换后nums = [5,2,4]。 - 元素对
(2,4)的和为 6。替换后nums = [5,6]。
数组 nums 在两次操作后变为非递减。
示例 2：
输入： nums = [1,2,2]
输出： 0
解释：
数组 nums 已经是非递减的。
提示：
1 <= nums.length <= 50-1000 <= nums[i] <= 1000
解题思路
方法一：模拟
我们定义一个函数 ，用于判断数组 是否为非递减数组。
我们使用一个循环，直到数组 为非递减数组为止。在每次循环中，我们找到数组 中相邻元素对的和的最小值，并记录该对的左边元素的下标 。然后，我们将该对的和替换左边的元素，并删除右边的元素。最后，我们返回操作的次数。
时间复杂度 ，空间复杂度 。其中 为数组的长度。
class Solution:
def minimumPairRemoval(self, nums: List[int]) -> int:
arr = nums[:]
ans = 0
def is_non_decreasing(a: List[int]) -> bool:
for i in range(1, len(a)):
if a[i] < a[i - 1]:
return False
return True
while not is_non_decreasing(arr):
k = 0
s = arr[0] + arr[1]
for i in range(1, len(arr) - 1):
t = arr[i] + arr[i + 1]
if s > t:
s = t
k = i
arr[k] = s
arr.pop(k + 1)
ans += 1
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is driven by the scanning of the array and the hash lookup process. In the worst case, it will be O(n) where n is the length of the array. Space complexity depends on the data structure used for tracking pairs, but it typically remains O(n) as well. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Can the candidate effectively track removable pairs using a hash table?
- question_mark
Does the candidate approach the problem using greedy techniques?
- question_mark
Is the candidate able to optimize the algorithm to reduce unnecessary steps?
常见陷阱
外企场景- error
Failing to consider the order of removals, which could lead to unnecessary operations.
- error
Not efficiently using hash lookups to reduce the number of pair checks.
- error
Misunderstanding the definition of 'non-decreasing' and attempting unnecessary operations.
进阶变体
外企场景- arrow_right_alt
What if the array contains only one element?
- arrow_right_alt
Can this problem be solved by applying dynamic programming?
- arrow_right_alt
How would the approach change if you could remove more than one pair per operation?