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

2021-05-04 12:07:42

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）
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

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[0] = 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://chowdera.com/2021/05/20210504120226065h.html