1846.maximum element after decreasing and rearranging 减小和重新排列数组后的最大元素

问题描述

1846.减小和重新排列数组后的最大元素

解题思路

由于题目允许我们重新排列数组中的元素任意次，因此首先将数组排序，根据arr中第一个元素必须为1，以及相邻两元素的差的绝对值小于等于1，可得arr[i] = min(i + 1, arr[i - 1] + 1)（因为我们要找arr可能的最大值），又因为不允许增大arr中的元素，所以arr[i] = min(arr[i], i + 1, arr[i - 1] + 1)。

代码

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 - 1] + 1, min(arr[i], i + 1));
        }
        return arr[arr.size() - 1];
    }
};