I give you an array of positive integers, ARr. You can do something (or nothing) to the ARR to make the array satisfy the following conditions:

  • The first element in arR must be 1.
  • The absolute value of the difference between any two adjacent elements is less than or equal to 1, that is, abs(arr[I] -arr [i-1]) <= 1 for any 1 <= I < arr.length (array subscripts start at 0). Abs of x is the absolute value of x.

You can perform the following two operations any time:

  • Reduces the value of any element in arR to a smaller positive integer.
  • Rearrange elements in arR, you can rearrange them in any order.

Return the maximum possible value in the ARR after performing the above operations under the conditions described above.

Example 1: Input: arr = [2,2,1,2,1] Output: 2 Explanation: We can rearrange arR to get [1,2,2,2,1], which satisfies all conditions. The largest element in ARR is 2. Example 2: input: arr = [100,1,1000] output: 3 explanation: a possible solution is as follows: 1. Rearranging arr yields [1,100,1000]. 2. Reduce the second element to 2. 3. Reduce the third element to 3. Now arr = [1,2,3] satisfies all conditions. The largest element in ARR is 3. Example 3: input: arr = [1,2,3,4,5] output: 5 explanation: all conditions are met for the array, and the maximum element is 5.Copy the code

Their thinking

  1. Since the first element in arR must be 1, the absolute value of the difference between any two adjacent elements is less than or equal to 1, and to get the maximum, our rearranged array only needs to be non-decrement.
  2. Because our target array is a non-decrement array and we can rearrange elements in the ARR, we can arrange the array from smallest to largest. Therefore, the final constructed target array is [1,1,1,2,3,4,5…. Max], and Max is the maximum value. (Since we can directly reduce the obsolete arr[I] to 1, any element can become 1, so 1 is not involved in the target array discussion.)
  3. Since the elements of ARR can only be reduced, arr[I] must be greater than the target value in order to be converted to the target value

The array [1,2,3,4,5…. Max] is the dragon’s ability value, we need to select Max warriors, each warrior’s ability value is greater than the dragon’s ability value

So you can be greedy, sort your arr, and choose warriors from the smallest to the largest to deal with dragons with abilities of [1,2,3,4,5…. Max]

code

class Solution {
    public int maximumElementAfterDecrementingAndRearranging(int[] arr) {

        int n=arr.length,tar=1;
        Arrays.sort(arr);
        for (int i=0; i<n; i++) {if(tar<=arr[i])
                tar++;
        }
        return tar-1; }}Copy the code