Hard

题目描述

给你一个整数数组 target ，包含 n 个整数。从一个由 n 个 1 组成的初始数组 arr 开始，你可以执行以下过程：

  • 设 x 为你当前数组里所有元素的和。
  • 选择满足 0 <= i < n 的任意下标 i ，并将 arr[i] 的值设为 x 。
  • 你可以重复这个过程任意次。

如果能从 arr 构造出 target 数组，请返回 true ；否则，返回 false 。

示例 1：

输入：target = [9,3,5]
输出：true
解释：从 arr = [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 <= n <= 5 * 10^4
  • 1 <= target[i] <= 10^9

解题思路

解题思路

这道题的关键洞察是：逆向思考。

由于每次操作都会将某个位置的值设为当前数组的总和，而总和是严格递增的，这意味着目标数组中的最大值一定是最后一步生成的。因此，我们可以从目标状态开始，逆向模拟这个过程。

核心思想：

  1. 最大堆维护：使用最大堆来快速找到当前最大值
  2. 逆向操作：当前最大值 = 前一步的总和，所以前一步该位置的值 = 当前最大值 - (当前总和 - 当前最大值)
  3. 终止条件：当所有元素都变为1时成功；如果过程中出现非法值则失败

算法步骤：

  1. 将所有元素放入最大堆，计算总和
  2. 取出最大值，计算其他元素的和
  3. 如果最大值 <= 其他元素和，说明无法构造
  4. 计算前一步该位置的值，将其放回堆中
  5. 重复直到所有元素都为1

优化点：

当其他元素和为1时（即只有两个元素且其中一个为1），可以直接通过模运算快速计算，避免超时。

推荐解法是使用最大堆的逆向模拟，时间复杂度相对较优。

代码实现

class Solution {
public:
    bool isPossible(vector<int>& target) {
        if (target.size() == 1) return target[0] == 1;
        
        priority_queue<long long> pq;
        long long total = 0;
        
        for (int x : target) {
            pq.push(x);
            total += x;
        }
        
        while (pq.top() != 1) {
            long long largest = pq.top();
            pq.pop();
            long long rest = total - largest;
            
            if (rest == 1) {
                return true;
            }
            
            if (rest == 0 || largest <= rest) {
                return false;
            }
            
            long long prev = largest % rest;
            if (prev == 0) prev = rest;
            
            pq.push(prev);
            total = rest + prev;
        }
        
        return true;
    }
};

class Solution:
    def isPossible(self, target: List[int]) -> bool:
        if len(target) == 1:
            return target[0] == 1
        
        import heapq
        # Python的heapq是最小堆，所以存储负值来模拟最大堆
        heap = [-x for x in target]
        heapq.heapify(heap)
        total = sum(target)
        
        while -heap[0] != 1:
            largest = -heapq.heappop(heap)
            rest = total - largest
            
            if rest == 1:
                return True
            
            if rest == 0 or largest <= rest:
                return False
            
            prev = largest % rest
            if prev == 0:
                prev = rest
            
            heapq.heappush(heap, -prev)
            total = rest + prev
        
        return True

public class Solution {
    public bool IsPossible(int[] target) {
        if (target.Length == 1) return target[0] == 1;
        
        var pq = new PriorityQueue<long, long>(Comparer<long>.Create((a, b) => b.CompareTo(a)));
        long total = 0;
        
        foreach (int x in target) {
            pq.Enqueue(x, x);
            total += x;
        }
        
        while (pq.Peek() != 1) {
            long largest = pq.Dequeue();
            long rest = total - largest;
            
            if (rest == 1) {
                return true;
            }
            
            if (rest == 0 || largest <= rest) {
                return false;
            }
            
            long prev = largest % rest;
            if (prev == 0) prev = rest;
            
            pq.Enqueue(prev, prev);
            total = rest + prev;
        }
        
        return true;
    }
}

var isPossible = function(target) {
    if (target.length === 1) return target[0] === 1;
    
    let totalSum = target.reduce((sum, num) => sum + num, 0);
    let maxHeap = new MaxPriorityQueue();
    
    for (let num of target) {
        maxHeap.enqueue(num);
    }
    
    while (maxHeap.front().element > 1) {
        let largest = maxHeap.dequeue().element;
        let restSum = totalSum - largest;
        
        if (restSum === 1) return true;
        if (restSum === 0 || largest <= restSum) return false;
        
        let newVal = largest % restSum;
        if (newVal === 0) {
            if (restSum !== 1) return false;
            newVal = restSum;
        }
        
        maxHeap.enqueue(newVal);
        totalSum = restSum + newVal;
    }
    
    return true;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n log n log M)，其中 n 是数组长度，M 是最大元素值。每次操作需要 O(log n) 的堆操作，最多需要 O(log M) 次迭代
空间复杂度O(n)，用于存储堆

相关题目