1846.maximum element after decreasing and rearranging

Description Link to heading

1846.maximum-element-after-decreasing-and-rearranging

Solution Link to heading

Since we can reorder the element in the array as many times as we like, so we should sort the array first. If we want to find the possible maximum number of array whose the first element must be 1 and the absolute difference of any 2 adjacent differences must be less or equal to 1， so we can get arr[i] = min(i + 1, arr[i - 1] + 1). We can’t increase the element in the array, so arr[i] = min(arr[i], i + 1, arr[i - 1] + 1).

Code Link to heading

class Solution {
public:
    int maximumElementAfterDecrementingAndRearranging(vector<int>& arr) {
        sort(arr.begin(), arr.end());
        arr[0] = 1;
        for (int i = 1; i < arr.size(); i++) {
            arr[i] = min(arr[i - 1] + 1, min(arr[i], i + 1));
        }
        return arr[arr.size() - 1];
    }
};