【LeetCode】 1846. Maximum Element After Decreasing and Rearranging

Description

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.

Constraints:

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

給你一個正整數的陣列 arr。 對 arr 執行幾種操作(也可能不做任何事)使其滿足以下條件：

• arr 中的第一個元素必須是 1。
• 兩個相鄰元素的絕對值必須小於等於 1。換句話說，abs(arr[i] - arr[i - 1]) <= 1 對於任何 i 為 1 <= i < arr.length （索引值從 0 開始）。abs(x) 是 x 的絕對值.

有兩種操作你可以執行任意次數：

• 減少 arr 中任意元素的值變為更小的正整數。
• 重新排列 arr 的元素變為任意順序。

回傳 arr 經過操作並滿足條件時，陣列中可能的最大值為多少。

限制：

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

Example:

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.

Solution

• 沒有限制操作的次數，因此可以簡化思路
• 我們先將陣列由小到大排序，接著將第一個元素改為 1
• 從第二的元素開始遍歷整個陣列，記錄當下的最大值
• 第二的元素有兩種可能：
  • 大於等於 2，將最大值紀錄為 2（因為絕對值最多只能是 1）
  • 小於 2，最大值不變
• 第三個元素開始以此類推，只會有兩種可能
  • 大於等於當前最大值
  • 小於當前最大值

Code

class Solution {
public:
    int maximumElementAfterDecrementingAndRearranging(vector<int>& arr) {
        int ans = 1;
        sort(arr.begin(), arr.end());

        for(int i = 1; i < arr.size(); i++)
        {
            if(arr[i] > ans)
                ans++;
        }
        return ans;
    }
};

tags: LeetCode C++