多次求和构造目标数组

难度: Hard

给你一个整数数组 target 。一开始，你有一个数组 A ，它的所有元素均为 1 ，你可以执行以下操作：

令 x 为你数组里所有元素的和
选择满足 0 <= i < target.size 的任意下标 i ，并让 A 数组里下标为 i 处的值为 x 。
你可以重复该过程任意次

如果能从 A 开始构造出目标数组 target ，请你返回 True ，否则返回 False 。

示例 1：

输入：target = [9,3,5]
输出：true
解释：从 [1, 1, 1] 开始
[1, 1, 1], 和为 3 ，选择下标 1
[1, 3, 1], 和为 5， 选择下标 2
[1, 3, 5], 和为 9， 选择下标 0
[9, 3, 5] 完成

示例 2：

输入：target = [1,1,1,2]
输出：false
解释：不可能从 [1,1,1,1] 出发构造目标数组。

示例 3：

输入：target = [8,5]
输出：true

提示：

N == target.length
1 <= target.length <= 5 * 10^4
1 <= target[i] <= 10^9

Submission

运行时间: 30 ms

内存: 21.1 MB

class Solution:
    def isPossible(self, target: List[int]) -> bool:
        if len(target)==1:
            return target[0]==1
        s=sum(target)
        target=[-v for v in target]
        heapify(target)
        while target[0]<-1:
            p=-heappop(target)
            a=-target[0]
            if a==p:
                return False
            rest=s-p
            #数学公式优化转移
            k=ceil((p-a)/rest)
            p-=k*rest
            if p<1:
                return False
            s-=k*rest
            heappush(target,-p)
        return True

Explain

题解使用了反向操作的思路，即从target数组反推回初始数组，看是否所有元素均能变为1。主要思路是使用最大堆（通过存储负数来使用Python的最小堆实现最大堆的效果），每次从堆中取出当前最大的元素，计算这个元素与其他元素总和的差，即是上一次操作后该位置的值。如果在任何时刻，最大元素值减去其他元素的总和小于1，说明无法通过加法操作得到该值，返回False。继续这个过程，直到所有元素变为1。这个方法利用了每次操作对数组的最大值影响最大的特性，从而反向模拟得到是否可行。

时间复杂度: O(n log m) ，其中n是target数组的长度，m是target数组中元素的最大值。

空间复杂度: O(n)

class Solution:
    def isPossible(self, target: List[int]) -> bool:
        if len(target) == 1: # 只有一个元素时，必须是1
            return target[0] == 1
        s = sum(target) # 计算总和
        target = [-v for v in target] # 转为最大堆需要的形式
        heapify(target) # 建立最大堆
        while target[0] < -1: # 当堆中最大值大于1时继续
            p = -heappop(target) # 获取并移除最大值
            a = -target[0] # 当前第二大的值
            if a == p: # 如果最大值和第二大值相等，则无法进行操作
                return False
            rest = s - p # 其他元素的总和
            k = ceil((p - a) / rest) # 计算需要减去的次数
            p -= k * rest # 更新最大值
            if p < 1: # 如果更新后的值小于1，则无法形成该数组
                return False
            s -= k * rest # 更新总和
            heappush(target, -p) # 将更新后的最大值重新放入堆中
        return True # 如果所有值都减到1，返回True

Explore

在反向操作中选择从最大元素开始处理的原因是因为在多次求和的操作过程中，每次操作的结果主要受到当前数组中最大值的影响。从最大值开始反推可以更直接地模拟回溯到初始数组的过程。如果最大值可以通过减去其他元素的总和的方式逐步减小到1，那么这种反推是成功的。另外，这样的操作还可以有效减少计算次数，因为最大值的变化直接决定了数组是否可以继续进行反推。

在算法中，`ceil((p - a) / rest)`的计算用来确定将最大值p减小至小于或等于次大值a所需的最小次数。这里的rest代表除了最大值p之外其他所有元素的总和。由于每次操作都是将最大值p减去rest，所以，为了使p尽可能快地减到a或者更小，需要计算p减去rest的次数。使用`ceil`函数是因为即使除法结果为非整数，也需要将次数向上取整，确保最大值p在足够的操作次数后能够小于或等于a。这个计算对于加速算法进程和确保算法的正确逻辑非常关键。

这一步是检查在反向操作过程中是否存在无法通过加法操作得到当前数组的情况。具体来说，如果在任何时刻，从堆中取出的当前最大元素值减去其他元素的总和小于1，说明这个最大元素无法通过之前的加法操作形成，因为每次操作至少增加1。这是一个基本的验证步骤，用来确保所有元素都可以有效地通过反向操作减小到1。如果不满足这一条件，则说明目标数组不可能通过一系列加法操作从全1数组开始构造得到，算法应当返回False。

当最大值和第二大值相等时，判断为无法进行操作并返回False是因为在这种情况下，无法通过正常的加法操作区分这两个值。在正常的多次求和操作中，每一次操作都会使得某一个元素（最大元素）显著增加，而其他元素相对较小或不变。如果两个最大值相等，说明没有任何单次操作可以使一个元素成为独立的最大值，从而违反了这种操作逻辑。因此，这种情况下目标数组不能通过从全1数组的多次求和操作得到。