## Leetcode 1846. Reduce and rearrange the largest element of an array

Michael Amin 2021-05-04 12:07:42
leetcode reduce rearrange largest element

## 1. subject

To give you one Positive integer Array arr . Please be right arr Do something （ You can also do nothing ）, Make the array satisfy the following conditions ：

• arr in first The element must be 1 .
• arbitrarily adjacent The absolute value of the difference between two elements Less than or equal to 1 , in other words , For arbitrary `1 <= i < arr.length` （ Array index from 0 Start ）, All satisfied with `abs(arr[i] - arr[i - 1]) <= 1` .abs(x) by x The absolute value of .

You can do the following 2 Any number of operations ：

• Reduce arr The value of any element in , Make it a Smaller positive integers .
• Rearrange arr The elements in , You can rearrange it in any order .

Please return to after performing the above operation , Under the conditions mentioned above ,arr It's possible that Maximum .

`````` Example 1：
Input ：arr = [2,2,1,2,1]
Output ：2
explain ：
We can rearrange arr obtain [1,2,2,2,1] , The array satisfies all the conditions .
arr The largest element in this series is 2 .
Example 2：
Input ：arr = [100,1,1000]
Output ：3
explain ：
A feasible solution is as follows ：
1. Rearrange arr obtain [1,100,1000] .
2. Reduce the second element to 2 .
3. Reduce the third element to 3 .
Now? arr = [1,2,3] , All conditions are met .
arr The largest element in this series is 3 .
Example 3：
Input ：arr = [1,2,3,4,5]
Output ：5
explain ： The array has met all the conditions , The largest element is 5 .
Tips ：
1 <= arr.length <= 10^5
1 <= arr[i] <= 10^9
``````

source ： Power button （LeetCode）

## 2. Problem solving

• According to the meaning of the title , Can sort , The first is 1, Then check in turn if the gap is greater than 1, Greater than 1 So the gap is 1, You can make the largest number the largest
``````class Solution {

public:
int maximumElementAfterDecrementingAndRearranging(vector<int>& arr) {

sort(arr.begin(), arr.end());
arr = 1;
for(int i = 1; i < arr.size(); i++)
{

if(arr[i] - arr[i-1] > 1)
{

arr[i] = arr[i-1]+1;
}
}
return arr.back();
}
};
``````

100 ms 50.1 MB C++

Long click or sweep code pay attention to my official account （Michael amin ）, Come on together 、 Learn together ！ https://qdmana.com/2021/05/20210504120226065h.html