减小和重新排列数组后的最大元素」,难度为 「中等」。
Tag : 「贪心」
给你一个正整数数组 arr。...你可以执行以下
2
种操作任意次:
减小 arr 中任意元素的值,使其变为一个更小的正整数
重新排列 arr 中的元素,你可以以任意顺序重新排列
请你返回执行以上操作后,在满足前文所述的条件下,arr...示例 1:
输入:arr = [2,2,1,2,1]
输出:2
解释:
我们可以重新排列 arr 得到 [1,2,2,2,1] ,该数组满足所有条件。
arr 中最大元素为 2 。...重新排列 arr 得到 [1,100,1000] 。
2. 将第二个元素减小为 2 。
3. 将第三个元素减小为 3 。
现在 arr = [1,2,3] ,满足所有条件。...证明三:调整大小的操作不会改变数组元素之间的相对位置关系。
在证明二的分析中,我们会对某些元素进行“减小”操作,使得整个数组最终满足「相邻位差值绝对值不超过
1
」。