题目

https://leetcode-cn.com/problems/maximum-element-after-decreasing-and-rearranging/

方法一、排序+贪心

这种方法比较好理解

思路

  • 如果一个数组是满足要求的，那么将它的元素按照升序排序后得到的数组也是满足要求的。
  • 那么数组中相邻两个元素，要么后者等于前者，要么后者等于前者加上 1。

  • 最终的答案（最大值）即为 arr 中的最后一个元素。

    代码

    1. public static int maximumElementAfterDecrementingAndRearranging(int[] arr) {
    3.   // 从小到大排序 arr
    4.   Arrays.sort(arr);
    5.   // 初始化data 0位置为1，直接把arr第0位舍弃掉，因为不管他是不是1我们都要给他改成1
    6.   arr[0] = 1;
    7.   // 循环arr，判断下标位置i与下标i-1的差值，如果大于1就改为data[i-1]+1，否则就赋值为arr[i]
    8.   for (int i = 1; i < arr.length; i++) {
    9.       if (arr[i] - arr[i - 1] > 1) {
    10.           arr[i] = arr[i - 1] + 1;
    11.       }
    12.   }
    13.   return arr[arr.length-1];
    14. }

    复杂度分析

    时间复杂度：O(nlogn)，其中 nn 是数组 \textit{arr}arr 的长度。时间复杂度即排序的复杂度。
    空间复杂度：O(logn)。空间复杂度不考虑输入，因此空间复杂度主要取决于排序时产生的 O(\log n)O(logn) 的栈空间。

    方法二、计数排序 + 贪心

    官方解析里的，没看懂。