# 【LeetCode】 1846. Maximum Element After Decreasing and Rearranging
## Description
> You are given an array of positive integers `arr`. Perform some operations (possibly none) on `arr` so that it satisfies these conditions:
> * The value of the first element in `arr` must be `1`.
> * The absolute difference between any 2 adjacent elements must be less than or equal to `1`. In other words, `abs(arr[i] - arr[i - 1]) <= 1` for each `i` where `1 <= i < arr.length` (0-indexed). `abs(x)` is the absolute value of `x`.
> There are 2 types of operations that you can perform any number of times:
> * Decrease the value of any element of `arr` to a smaller positive integer.
> * Rearrange the elements of `arr` to be in any order.
> Return the maximum possible value of an element in `arr` after performing the operations to satisfy the conditions.
> Constraints:
> * `1 <= arr.length <= 105`
> * `1 <= arr[i] <= 109`
> 給你一個正整數的陣列 `arr`。 對 `arr` 執行幾種操作(也可能不做任何事)使其滿足以下條件:
> * `arr` 中的第一個元素必須是 `1`。
> * 兩個相鄰元素的絕對值必須小於等於 `1`。換句話說,`abs(arr[i] - arr[i - 1]) <= 1` 對於任何 `i` 為 `1 <= i < arr.length` (索引值從 `0` 開始)。`abs(x)` 是 `x` 的絕對值.
> 有兩種操作你可以執行任意次數:
> * 減少 `arr` 中任意元素的值變為更小的正整數。
> * 重新排列 `arr` 的元素變為任意順序。
> 回傳 `arr` 經過操作並滿足條件時,陣列中可能的最大值為多少。
> 限制:
> * `1 <= arr.length <= 105`
> * `1 <= arr[i] <= 109`
## Example:
```
Example 1:
Input: arr = [2,2,1,2,1]
Output: 2
Explanation:
We can satisfy the conditions by rearranging arr so it becomes [1,2,2,2,1].
The largest element in arr is 2.
```
```
Example 2:
Input: arr = [100,1,1000]
Output: 3
Explanation:
One possible way to satisfy the conditions is by doing the following:
1. Rearrange arr so it becomes [1,100,1000].
2. Decrease the value of the second element to 2.
3. Decrease the value of the third element to 3.
Now arr = [1,2,3], which satisfies the conditions.
The largest element in arr is 3.
```
```
Example 3:
Input: arr = [1,2,3,4,5]
Output: 5
Explanation: The array already satisfies the conditions, and the largest element is 5.
```
## Solution
* 沒有限制操作的次數,因此可以簡化思路
* 我們先將陣列由小到大排序,接著將第一個元素改為 `1`
* 從第二的元素開始遍歷整個陣列,記錄當下的最大值
* 第二的元素有兩種可能:
* 大於等於 `2`,將最大值紀錄為 `2`(因為絕對值最多只能是 `1`)
* 小於 `2`,最大值不變
* 第三個元素開始以此類推,只會有兩種可能
* 大於等於當前最大值
* 小於當前最大值
### Code
```C++=1
class Solution {
public:
int maximumElementAfterDecrementingAndRearranging(vector<int>& arr) {
int ans = 1;
sort(arr.begin(), arr.end());
for(int i = 1; i < arr.size(); i++)
{
if(arr[i] > ans)
ans++;
}
return ans;
}
};
```
###### tags: `LeetCode` `C++`