Medium

题目描述

给你一个正整数数组 arr。请你对 arr 执行一些操作（也可以不进行操作），使其满足以下条件：

  • arr 中第一个元素的值为 1
  • 任意相邻两个元素的绝对差小于等于 1，也就是说，对于每个 i（1 <= i < arr.length），都满足 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 <= 10^5
  • 1 <= arr[i] <= 10^9

解题思路

这道题的核心思路是贪心算法结合排序。

首先分析题目要求：

  1. 第一个元素必须是1
  2. 相邻元素的绝对差不超过1
  3. 我们可以减少任意元素的值，也可以重新排列数组

为了得到最大可能的元素值，我们应该：

贪心策略：

  • 将数组按升序排序，这样可以最大化利用每个位置
  • 第一个位置固定为1
  • 对于后续每个位置，我们希望元素值尽可能大，但不能超过前一个元素+1

具体步骤：

  1. 对数组进行升序排序
  2. 第一个元素设为1
  3. 从第二个元素开始，每个位置的值取 min(当前元素值, 前一个元素值 + 1)
  4. 最终数组的最后一个元素就是答案

为什么这样是最优的？

  • 排序后，我们从小到大处理元素，确保每个位置都能达到理论最大值
  • 每个位置最多比前一个位置大1，所以第i个位置（0-indexed）的理论最大值是i+1
  • 如果原数组中某个元素本身就很大，我们尽量保持它，如果太大就减少到允许的最大值

时间复杂度主要来自排序，为O(n log n)。

代码实现

class Solution {
public:
    int maximumElementAfterDecrementingAndRearranging(vector<int>& arr) {
        sort(arr.begin(), arr.end());
        
        arr[0] = 1;
        for (int i = 1; i < arr.size(); i++) {
            arr[i] = min(arr[i], arr[i-1] + 1);
        }
        
        return arr.back();
    }
};

class Solution:
    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:
        arr.sort()
        
        arr[0] = 1
        for i in range(1, len(arr)):
            arr[i] = min(arr[i], arr[i-1] + 1)
        
        return arr[-1]

public class Solution {
    public int MaximumElementAfterDecrementingAndRearranging(int[] arr) {
        Array.Sort(arr);
        
        arr[0] = 1;
        for (int i = 1; i < arr.Length; i++) {
            arr[i] = Math.Min(arr[i], arr[i-1] + 1);
        }
        
        return arr[arr.Length - 1];
    }
}

var maximumElementAfterDecrementingAndRearranging = function(arr) {
    arr.sort((a, b) => a - b);
    
    arr[0] = 1;
    for (let i = 1; i < arr.length; i++) {
        arr[i] = Math.min(arr[i], arr[i-1] + 1);
    }
    
    return arr[arr.length - 1];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log n)主要来自排序操作
空间复杂度O(1)只使用了常数额外空间（原地修改数组）