LeetCode 题解工作台
减小和重新排列数组后的最大元素
给你一个正整数数组 arr 。请你对 arr 执行一些操作（也可以不进行任何操作），使得数组满足以下条件： arr 中 第一个 元素必须为 1 。 任意相邻两个元素的差的绝对值 小于等于 1 ，也就是说，对于任意的 1 （ 数组下标从 0 开始 ），都满足 abs(arr[i] - arr[i - …
3
题型
6
代码语言
3
相关题
当前训练重点
中等 · 贪心·invariant
答案摘要
我们先对数组进行排序，然后将数组的第一个元素设置为 。 接下来，我们从第二个元素开始遍历数组，如果当前元素与前一个元素的差值大于 ，我们就贪心地将当前元素减小为前一个元素加 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 贪心·invariant 题型思路
题目描述
给你一个正整数数组 arr 。请你对 arr 执行一些操作（也可以不进行任何操作），使得数组满足以下条件：
arr中 第一个 元素必须为1。- 任意相邻两个元素的差的绝对值 小于等于
1，也就是说，对于任意的1 <= i < arr.length（数组下标从 0 开始），都满足abs(arr[i] - arr[i - 1]) <= 1。abs(x)为x的绝对值。
你可以执行以下 2 种操作任意次：
- 减小
arr中任意元素的值，使其变为一个 更小的正整数 。 - 重新排列
arr中的元素，你可以以任意顺序重新排列。
请你返回执行以上操作后，在满足前文所述的条件下，arr 中可能的 最大值 。
示例 1：
输入：arr = [2,2,1,2,1]
输出：2
解释：
我们可以重新排列 arr 得到 [1,2,2,2,1] ，该数组满足所有条件。
arr 中最大元素为 2 。
示例 2：
输入：arr = [100,1,1000] 输出：3 解释： 一个可行的方案如下： 1. 重新排列arr得到[1,100,1000] 。2. 将第二个元素减小为 2 。 3. 将第三个元素减小为 3 。 现在arr = [1,2,3] ，满足所有条件。arr 中最大元素为 3 。
示例 3：
输入：arr = [1,2,3,4,5] 输出：5 解释：数组已经满足所有条件，最大元素为 5 。
提示：
1 <= arr.length <= 1051 <= arr[i] <= 109
解题思路
方法一：排序 + 贪心
我们先对数组进行排序，然后将数组的第一个元素设置为 。
接下来，我们从第二个元素开始遍历数组，如果当前元素与前一个元素的差值大于 ，我们就贪心地将当前元素减小为前一个元素加 。
最后，我们返回数组中的最大元素。
时间复杂度 ，空间复杂度 。其中 为数组长度。
class Solution:
def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:
arr.sort()
arr[0] = 1
for i in range(1, len(arr)):
d = max(0, arr[i] - arr[i - 1] - 1)
arr[i] -= d
return max(arr)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(n) |
| 空间 | O(n) |
面试官常问的追问
外企场景- question_mark
Look for sorting the array before applying operations.
- question_mark
Check if each element can be at most one greater than its previous.
- question_mark
Validate the maximum value after greedy adjustments.
常见陷阱
外企场景- error
Forgetting to sort before applying greedy decreases.
- error
Not enforcing the invariant that arr[i] <= arr[i-1] + 1.
- error
Returning the initial max instead of the adjusted maximum element.
进阶变体
外企场景- arrow_right_alt
Find maximum after only decreasing elements without rearranging.
- arrow_right_alt
Return the array configuration instead of just the maximum element.
- arrow_right_alt
Apply the same approach for arrays with negative numbers allowed.