This article is participating in Python Theme Month. See the link for details

Topic describes

This is 1846 on LeetCode. Maximum element after decrement and rearrangement of array, medium difficulty.

Tag: “Greedy.”

I give you an array of positive integers, ARr. You can do something (or nothing) to the ARR to make the array satisfy the following conditions:

  • The first element in arR must be 1.
  • The absolute value of the difference between any two adjacent elements is less than or equal to 1, that is, abs(arr[I] -arr [i-1]) <= 1 for any 1 <= I < arr.length (array subscripts start at 0). Abs of x is the absolute value of x.

You can perform the following two operations any time:

  • Reduces the value of any element in arR to a smaller positive integer.
  • Rearrange elements in arR, you can rearrange them in any order.

Return the maximum possible value in the ARR after performing the above operations under the conditions described above.

Example 1:

Input: arr = [2,2,1,2,1] output: 2 explanation: we can rearrange arr to get [1,2,2,2,1], which satisfies all conditions. The largest element in ARR is 2.Copy the code

Example 2:

Input: arr = [100,1,1000] output: 3 explanation: a possible solution is as follows: 1. Rearranging arr yields [1,100,1000]. 2. Reduce the second element to 2. 3. Reduce the third element to 3. Now arr = [1,2,3] satisfies all conditions. The largest element in ARR is 3.Copy the code

Example 3:

Input: arr = [1,2,3,4,5] output: 5Copy the code

Tip:

  • 1 <= arr.length <=
    1 0 5 10^5

1 <= arr[i] <=
1 0 9 10^9

Basic analysis & proof

The first digit of the array must be 111, and each number can only be reduced or fixed. The position of the number can be adjusted arbitrarily.

Find out what the maximum size of the array is after adjustment.

First of all, the absolute value of the difference between adjacent bits of the qualified array does not exceed 111, which defines that the array must be one of the following three distributions:

  • (not strictly) decreasing monotonously
  • There is band
  • (not strictly) monotonically increasing

Proof 1: The array corresponding to the optimal solution “must be” or “can be adjusted to” (not strictly) monotonically increasing form.

We use inverse proof to prove that the other two distributions cannot obtain optimal solutions:

  • (non-strictly) monotone decrement: the number in the range of positive integers with the first digit 111 is not discussed, skip;
  • There are wave bands: We can always incorporate the values appearing on the right side of the wave peak into the left side of the wave peak, thereby eliminating the wave peak, and eventually adjust the whole distribution to the form of “(non-strictly) monotonically increasing”, the result will not be worse:

The same is true for multiple wavelengths, where you can draw on paper yourself.

Both use points to the right of the crest to be adjusted to the left of the crest, thus making the distribution (not strictly) monotonically increasing.

At this point, we prove that the array corresponding to the optimal solution must be monotonically increasing.

This inspires us to sort the original array first and analyze on this basis.

The ordered array obtained by sorting the original array does not necessarily conform to “the absolute value of the difference between adjacent bits does not exceed 111”, and each value can be reduced or fixed.

Proof 2: When it is necessary to adjust the current bit, the preference is to adjust the difference between the current bit and the previous value
1 1 The greater number of “will not be adjusted to” the difference from the previous value is
0 0 Is worse than a decimal number.

This can be done by inductive reasoning, assuming that the sequence a is obtained by taking “priority adjustment to the larger number with a difference of 111 from the previous value”, and the sequence B is obtained by taking “priority adjustment to the smaller number with a difference of 000 from the previous value”.

According to the”
a [ 0 ] = b [ 0 ] = 1 a[0] = b[0] = 1 “,”a 和 bOf the same length.a 和 bAre (not strictly) monotonically increasing “and”a 和 bAll of them satisfy that the difference between adjacent bits does not exceed
1 1 “, can be derived
s u m ( a ) > = s u m ( b ) sum(a) >= sum(b) , and any position
a [ i ] > = b [ i ] a[i] >= b[i] And then we deriveaThe last digit of the sequence must be greater than or equal tobThe last digit of the.

B can’t be better than A.

Proof 3: Resizing does not change the relative positions of array elements.

In the analysis of proof 2, we will “reduce” some elements so that the entire array ends up with “the absolute value of the difference between adjacent bits does not exceed 111”.

But the proof works only if the adjustment does not rearrange the original elements.

So is the premise necessarily true? The answer is yes.

Suppose there are points III and JJJ that need to be adjusted in the original sorted array, and NUMs [I]<=nums[j]nums[I]<=nums[j]nums[I]<=nums[j].

Nums [p]>= NUMs [q]nums[p]>=nums[q] nums[p] =nums[q]

At this point, we can make sure that the same condition is met by adjusting their variation relationship: point III becomes point QQQ, and point JJJ becomes point PPP, without triggering a rearrangement of the elements in the ordered array.

greedy

Sort, limit the first value to 111, process from front to back, make a decision according to whether each bit “must be modified (whether the difference with the last bit is greater than 111)”, if it must be modified, modify to the larger number with the difference with the previous value of 111.

Java code:

class Solution {
    public int maximumElementAfterDecrementingAndRearranging(int[] arr) {
        int n = arr.length;
        Arrays.sort(arr);
        arr[0] = 1;
        for (int i = 1; i < n; i++) {
            if (arr[i] - arr[i - 1] > 1) {
                arr[i] = arr[i - 1] + 1; }}return arr[n - 1]; }}Copy the code

Python 3 code:

class Solution:
    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) - >int:
        n = len(arr)
        arr.sort()
        arr[0] = 1
        for i in range(1, n):
            if arr[i] - arr[i - 1] > 1:
                arr[i] = arr[i - 1] + 1
        return arr[n - 1]
Copy the code
  • Time complexity: assumedArrays.sortA two-axis quickrow implementation is used. Complexity of
    O ( n log ⁡ n ) O(n\log{n})
  • Spatial complexity: assumedArrays.sortA two-axis quickrow implementation is used. Complexity of
    O ( log ⁡ n ) O(\log{n})

The last

This is the No.1846 of our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 topics in LeetCode as of the start date, some of which have locks.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.