题目

给你一个整数数组 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

思路

PriorityQueue

解法

class Solution {
    public boolean isPossible(int[] target) {
        if(target.length == 1 && target[0] == 1)return true;
        else if(target.length == 1)return false;
        long sum = 0;
        PriorityQueue<Long> q = new PriorityQueue<>((a,b)->Long.compare(b,a));
        for (int i : target) {
            sum+=i;
            q.add((long)i);
        }
        
        while (!q.isEmpty()){
            Long poll = q.poll();
            if(poll == 1)return true;


            Long tmp = q.peek();
            
            long t = poll - tmp;
            long cnt = (t + (sum - poll -1))/(sum - poll);

            if(cnt == 0)return false;

            long tp = poll-cnt*(sum - poll);

            sum-=poll - tp;
            if(tp < 1){
                return false;
            }
            q.add(tp);
        }

        return false;
    }
}

总结

• 分析出几种情况，然后分别对各个情况实现