A.每日一题：1846. 减小和重新排列数组后的最大元素

题目链接：1846. 减小和重新排列数组后的最大元素（中等）

算法原理：

解法一：贪心+直接排序

7ms击败82.31%

时间复杂度O(n logn)

贪心思路很简单：将整个数组从小到大升序排序，由于所有数都≥1，因此将第一个元素设置为1，往后依次遍历，如果发现 arr[i]-arr[i-1]>1，就将 arr[i] 设置为 arr[i-1]+1，最终的 arr[n-1] 即为答案

解法二：贪心+计数排序

3ms击败98.01%

时间复杂度O(N)

对于最终的数组，从左往右看，第一个数是1，在持续递增的情况下，最后一个数最多为 n

这就意味着，原数组 arr 中所有＞n 的数都要减小到≤ n，因此 ≥ n 的数都可以视作 n，这样我们就确定好了上限，可以在 1~n 之间使用计数排序进行计算了~~

遍历数组，统计它们的个数数组，记 cnt[x]为 arr 中 x 的个数

和解法一相同，从左往右遍历一遍，假设现在遍历完 ≤ 4 的数，得到的最大值为2，那么我们继续遍历的过程中：

①如果 cnt[5]=2，新的最大值是多少？？第一个5减小为3，第二个5减小为4，这样就能续上了，最大值为4

②如果 cnt[5]=4，新的最大值是多少？？第一个5减小为3，第二个5减小为4，第三个5不变，第四个5不变，最大值为5

因此当遍历到 cnt[x]之前得到的最大值为 mx，那么到 cnt[x]的时候，我们可以将 mx 增大至 mx+cnt[x]，但这个数不能超过 x，因此计算式子为 mx=min(mx+cnt[x],x)

Java代码：

class Solution { //1846. 减小和重新排列数组后的最大元素 //解法一：贪心+直接排序 public int maximumElementAfterDecrementingAndRearranging(int[] arr) { int n=arr.length; Arrays.sort(arr); arr[0]=1; for(int i=1;i<n;i++) if(arr[i]-arr[i-1]>1) arr[i]=arr[i-1]+1; return arr[n-1]; } }

class Solution { //1846. 减小和重新排列数组后的最大元素 //解法二：贪心+计数排序 public int maximumElementAfterDecrementingAndRearranging(int[] arr) { int n=arr.length; int[] cnt=new int[n+1]; for(int x:arr) cnt[Math.min(n,x)]++; int mx=0; for(int x=1;x<=n;x++) mx=Math.min(mx+cnt[x],x); return mx; } }