Leetcode每日一题 —— 1846. 减小和重新排列数组后的最大元素

蛮力很舒服（

class Solution {

public:

    int maximumElementAfterDecrementingAndRearranging(vector<int>& arr) {

        std::sort(arr.begin(),arr.end());

        int lastv = 0;

        for(int i = 0; i < arr.size(); i++) {

            lastv = min(lastv + 1,arr[i]);

        }

        return lastv;

    }

};

非递减排列，首个元素必须是 1，然后开始递推，保持递增 1 且非递减的趋势。最后 arr 的最大值就是结果。

class Solution {

public:

    int maximumElementAfterDecrementingAndRearranging(vector<int>& arr) {

        // 修改后可以任意重新排列

        // 修改元素只能变得更小

        // 修改的目的是要符合题目对 arr 的要求



        // 第一个元素必须是 1，因此 arr 中最小的数必须修改成 1

        // 为了求最大值，可以按非递减顺序进行排列

        sort(arr.begin(),arr.end());

        arr[0]=1;

        for(int i=1;i<arr.size();i++){

            // 修改后尽量呈递增，但注意修改元素只能变得更小

            arr[i]=min(arr[i-1]+1,arr[i]);

        }

        return arr.back();

    }

};