Leetcode 1675. Minimize Deviation in Array

[Wizmann]

Description

Problem

给定一个正整数数组A。规定以下两种操作：

• 若A[i]是奇数，可以有A[i] = 2 * A[i]
• 若A[i]是偶数，可以有A[i] = A[i] / 2

每一个操作可以执行任意次。问在若干次操作之后，max(A[]) - min(A[])的最小值。

Solution

首先研究对A[i]的两种操作。

如果A[i]是偶数，那么它只能除2，直到结果为奇数为止。如果A[i]是奇数，它只能进行一次乘2操作，因为乘2之后A[i]就变成偶数了。

所以对于所有的数，其变化范围有：

• A[i]为偶数：A[i] = 2^k * x ∈ [x, 2^k * x]
• A[i]为奇数：A[i] = x ∈ [x, 2 * x]

因此数组变化后的上下界是确定的。
假设已经确定了变化后数组的最小值x。所以对于A[i] < x，则必须进行扩大操作，使其等于大于等于x的最小值。这样一来，我们确定了下界，同时使上界尽可能小，保证了解是最优的。

实现方法如下：

首先把A[i]化为其最小值，每次取出最小值做为下界，最大值做为上界，求当前上下界的差。
然后：

• 如果A[i]当前值不是其最大值，将A[i]进行乘2操作
• 如果A[i]当前值为其最大值，说明数组已经到达其最大下界，后续操作不会更新答案，终止操作。

Code