• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

[LeetCode] 1846. Maximum Element After Decreasing and Rearranging

开发技术 开发技术 5天前 4次浏览

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.

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.

Constraints:

  • 1 <= arr.length <= 105
  • 1 <= arr[i] <= 109

减小和重新排列数组后的最大元素。

给你一个正整数数组 arr 。请你对 arr 执行一些操作(也可以不进行任何操作),使得数组满足以下条件:

arr 中 第一个 元素必须为 1 。
任意相邻两个元素的差的绝对值 小于等于 1 ,也就是说,对于任意的 1 <= i < arr.length (数组下标从 0 开始),都满足 abs(arr[i] – arr[i – 1]) <= 1 。abs(x) 为 x 的绝对值。
你可以执行以下 2 种操作任意次:

减小 arr 中任意元素的值,使其变为一个 更小的正整数 。
重新排列 arr 中的元素,你可以以任意顺序重新排列。
请你返回执行以上操作后,在满足前文所述的条件下,arr 中可能的 最大值 。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/maximum-element-after-decreasing-and-rearranging
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路是贪心 + 排序。首先,排序了才能起码保证数组是非递减或者起码不是乱序的,同时只有排序了才能知道第一个元素是否是 1。从第二个元素开始,如果他与之前一个元素的差的绝对值大于 1 了,那么我们就试图改动那个较大的元素。最后返回数组的最后一个元素即可。

时间O(nlogn)

空间O(1)

Java实现

 1 class Solution {
 2     public int maximumElementAfterDecrementingAndRearranging(int[] arr) {
 3         Arrays.sort(arr);
 4         if (arr[0] != 1) {
 5             arr[0] = 1;
 6         }
 7         for (int i = 1; i < arr.length; i++) {
 8             if (Math.abs(arr[i] - arr[i - 1]) > 1) {
 9                 arr[i] = arr[i - 1] + 1;
10             }
11         }
12         return arr[arr.length - 1];
13     }
14 }

 

LeetCode 题目总结


程序员灯塔
转载请注明原文链接:[LeetCode] 1846. Maximum Element After Decreasing and Rearranging
喜欢 (0)