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 be1
. - 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 eachi
where1 <= i < arr.length
(0-indexed).abs(x)
is the absolute value ofx
.
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 rearrangingarr
so it becomes[1,2,2,2,1]
. The largest element inarr
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. Rearrangearr
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. Nowarr = [1,2,3], which
satisfies the conditions. The largest element inarr 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
Solution: Sort
arr[0] = 1,
arr[i] = min(arr[i], arr[i – 1] + 1)
ans = arr[n – 1]
Time complexity: O(nlogn)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 |
// Author: Huahua class Solution { public: int maximumElementAfterDecrementingAndRearranging(vector<int>& arr) { const int n = arr.size(); sort(begin(arr), end(arr)); arr[0] = 1; for (int i = 1; i < n; ++i) arr[i] = min(arr[i], arr[i - 1] + 1); return arr.back(); } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment