leetcode 1846. 减小和重新排列数组后的最大元素 中等

给你一个正整数数组arr。请你对arr执行一些操作也可以不进行任何操作使得数组满足以下条件arr中第一个元素必须为1。任意相邻两个元素的差的绝对值小于等于1也就是说对于任意的1 i arr.length数组下标从 0 开始都满足abs(arr[i] - arr[i - 1]) 1。abs(x)为x的绝对值。你可以执行以下 2 种操作任意次减小arr中任意元素的值使其变为一个更小的正整数。重新排列arr中的元素你可以以任意顺序重新排列。请你返回执行以上操作后在满足前文所述的条件下arr中可能的最大值。示例 1输入arr [2,2,1,2,1]输出2解释我们可以重新排列 arr 得到[1,2,2,2,1] 该数组满足所有条件。arr 中最大元素为 2 。示例 2输入arr [100,1,1000]输出3解释一个可行的方案如下 1. 重新排列arr得到[1,100,1000] 。2. 将第二个元素减小为 2 。 3. 将第三个元素减小为 3 。 现在arr [1,2,3] 满足所有条件。arr 中最大元素为 3 。示例 3输入arr [1,2,3,4,5]输出5解释数组已经满足所有条件最大元素为 5 。提示1 arr.length 10^51 arr[i] 10^9分析先将 arr 数组从小到大排序并将数组的第一位改成 1. 由于数组是非递减的因此之后如果需要调整一定是后一个数减小到前一个数 1要么就不调整。因此可以遍历整个数组找到调整后的最大值。class Solution { public: int maximumElementAfterDecrementingAndRearranging(vectorint arr) { sort(arr.begin(),arr.end()); int ans1,narr.size();arr[0]1; for(int i1;in;i) { if(arr[i]-arr[i-1]1)arr[i]arr[i-1]1; ansmax(arr[i],ans); } return ans; } };