给你一个正整数数组?arr?。请你对 arr?执行一些操作（也可以不进行任何操作），使得数组满足以下条件：
arr?中 第一个?元素必须为?1?。
任意相邻两个元素的差的绝对值 小于等于?1?，也就是说，对于任意的 1 <= i < arr.length?（数组下标从 0 开始），都满足?abs(arr[i] - arr[i - 1]) <= 1?。abs(x)?为?x?的绝对值。
你可以执行以下 2 种操作任意次：
1, 减小 arr?中任意元素的值，使其变为一个 更小的正整数?。
2, 重新排列?arr?中的元素，你可以以任意顺序重新排列。
请你返回执行以上操作后，在满足前文所述的条件下，arr?中可能的 最大值?。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-element-after-decreasing-and-rearranging
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
示例 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
?官方给出了两种解题思路
方法一：排序 + 贪心
提示 11
如果一个数组是满足要求的，那么将它的元素按照升序排序后得到的数组也是满足要求的。
提示 1?解释
假设数组中出现了元素 xx和 y，且 x<y，由于相邻元素差值的绝对值小于等于 11，那么区间 [x,y]内的所有整数应该都出现过。
只要我们令 xx和 y分别为数组中元素的最小值和最大值，就说明了将数组升序排序后，得到的结果是不会出现「断层」的，也就是满足要求的。
提示 2
在提示 1?的基础上，我们得到了一个单调递增的数组。那么数组中相邻两个元素，要么后者等于前者，要么后者等于前者加上 1。
我们可以先将数组进行升序排序，随后对数组进行遍历，将 arr[i] 更新为其自身与 arr[i-1]+1中的较小值即可。
最终的答案（最大值）即为 arr 中的最后一个元素
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/maximum-element-after-decreasing-and-rearranging/solution/jian-xiao-he-zhong-xin-pai-lie-shu-zu-ho-mzee/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
int cmp(int *a, int *b) {
return *a - *b;
}
int maximumElementAfterDecrementingAndRearranging(int *arr, int arrSize) {
qsort(arr, arrSize, sizeof(int), cmp);
arr[0] = 1;
for (int i = 1; i < arrSize; ++i) {
arr[i] = fmin(arr[i], arr[i - 1] + 1);
}
return arr[arrSize - 1];
}
方法二：计数排序 + 贪心的
深挖题目隐含的性质，我们可以将时间复杂度优化至 O(n)。
记arr 的长度为 n。由于第一个元素必须为 1，且任意两个相邻元素的差的绝对值小于等于 1，故答案不会超过 n。所以我们只需要对 arr 中值不超过 n 的元素进行计数排序，而对于值超过 n 的元素，由于其至少要减小到 n，我们可以将其视作 n。
读者可据此修改方法一中的排序代码，此处不再赘述，我们将重点转到另一种计算策略上。
从另一个视角来看，为了尽可能地构造出最大的答案，我们相当于是在用 arr 中的元素去填补自身在 [1,n] 中缺失的元素。
首先，我们用一个长为 n+1 的数组 cnt 统计arr 中的元素个数（将值超过 n 的元素视作 n）。然后，从 1?到 n?遍历 cnt 数组，若 cnt[i]=0，则说明缺失元素 i，我们需要在后续找一个大于 i 的元素，将其变更为 i。我们可以用一个变量 miss 记录 cnt[i]=0 的出现次数，当遇到 cnt[i]>0 时，则可以将多余的 cnt[i]?1 个元素减小，补充到之前缺失的元素上。
遍历cnt 结束后，若此miss=0，则说明修改后的 arr 包含了[1,n] 内的所有整数；否则，对于不同大小的缺失元素，我们总是优先填补较小的，因此剩余缺失元素必然是 [n?miss+1,n] 这一范围内的miss 个数，因此答案为n?miss。
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/maximum-element-after-decreasing-and-rearranging/solution/jian-xiao-he-zhong-xin-pai-lie-shu-zu-ho-mzee/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
?
?
int maximumElementAfterDecrementingAndRearranging(int *arr, int arrSize) {
int cnt[arrSize + 1];
memset(cnt, 0, sizeof(cnt));
for (int i = 0; i < arrSize; i++) {
cnt[(int)fmin(arr[i], arrSize)]++;
}
int miss = 0;
for (int i = 1; i <= arrSize; ++i) {
if (cnt[i] == 0) {
++miss;
} else {
miss -= fmin(cnt[i] - 1, miss); // miss 不会小于 0，故至多减去 miss 个元素
}
}
return arrSize - miss;
}
|