LeetCode每日一题(1846. Maximum Element After Decreasing and Rearranging)

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

这题挺有意思的， 不过我不确定是不是有更简单的方法。
我们考虑两种情况:

1. 这种比较简单，就是数组里的数字没有重复的数字， 这样我们能拿到的最大值一定等于数组的长度。不明白的可以试着自己思考一下。
2. 数组里有重复数字的情况， 因为我们要使整个数组组成的数字最大， 所以我们遇到重复的数字最好的解决办法就是把它放到队尾去， 这时我们不单要考虑增加的情况， 还要考虑最终能降到这些重复的数字上的问题。现在我们把这个问题掰成两半来看， 我们将所有数字去掉重复的组成一个单向递增的数组， 递增 step 为 1， 然后我们将那些重复的剩下的数字组成一个单向递减的数组， 递减的 step 也为 1。这时候我们将两个数组拼合起来， 唯一可能会违反 step==1 这个条件的就只剩下这两个数组的接缝处了， 即 last(l1)与 first(l2), 我们现在能确定的是 last(l1) >= first(l2), 因为数字都优先供给 l1 了，只有重复的才会把剩下的留给 l2, 所以这时候实际控制最终答案的是 first(l2), 因为我们只能减小数字， 所以如果 last(l1) - first(l2) > 1 的话我们只能将 l1 中的数字都减小以适应 l2。

impl Solution {
    pub fn maximum_element_after_decrementing_and_rearranging(mut arr: Vec<i32>) -> i32 {
        arr.sort();
        let mut l1 = Vec::new();
        let mut l2 = Vec::new();
        for n in arr {
            if let Some(&last1) = l1.last() {
                if last1 == n {
                    if let Some(&last2) = l2.last() {
                        if n > last2 {
                            l2.push(last2 + 1);
                            continue;
                        }
                        l2.push(n);
                        continue;
                    }
                    l2.push(n);
                    continue;
                }
                l1.push(last1 + 1);
                continue;
            }
            l1.push(1);
        }
        if l2.is_empty() {
            return l1.pop().unwrap();
        }
        let last1 = l1.pop().unwrap();
        let last2 = l2.pop().unwrap();
        if last1 > last2 {
            return last2 + 1;
        }
        last1
    }
}