题目描述

点击查看题目

给你一个整数数组 target 。一开始，你有一个数组 A ，它的所有元素均为 1 ，你可以执行以下操作：
    令 x 为你数组里所有元素的和
    选择满足 0 <= i < target.size 的任意下标 i ，并让 A 数组里下标为 i 处的值为 x 。
    你可以重复该过程任意次
如果能从 A 开始构造出目标数组 target ，请你返回 True ，否则返回 False 。
示例

输入：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] 完成

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

思路

首先想到宽搜，按照规则逐级搜索，直到数组最大值大于目标数组的最大值。但观察数据规模，宽搜需要的队列占用空间会过于庞大，放弃搜索。

找到规律后倒推，倒推当前数组最大值之前的值为多少。

起始数组全为1，按照规则每次替换进数组的值，即当前数组之和，一定是新数组中的最大值，那么从目标数组倒推，其中最大值一定是上一次替换进来的值，也是上一次数组之和，并得到最大值位置上一次的数值，从而得到上一次的数组，不断倒推，直到数组最大值为1或数组之和为n，返回true，若过程中，出现非正数，返回false。

从样例说明，[9,3,5]，最大值为9，上一次数组之和为9，得到上一次的数组为[1,3,5]，重复此过程，得到[9,3,5]-->[1,3,5]-->[1,3,1]-->[1,1,1]。

变量说明：

max：当前数组最大值
sum：当前数组之和
max‘：最大值在上一次数组中的值，max'=max-(sum-max)=2*max-sum
sum'：上一次数组之和，sum'=sum-max+max'=sum-max+2*max-sum=max

 1 class Solution {
 2     public boolean isPossible(int[] target) {
 3         int L = target.length;
 4         long sum = 0;
 5         for (int value : target) sum += value;
 6         while (sum != L) {
 7             Arrays.sort(target);
 8             long max = target[L - 1];
 9             if (2 * max - sum < 1)
10                 return false;
11             else 
12                 target[L - 1] = (int) (2 * max - sum);
13             sum = max;
14         }
15         return true;
16     }
17 }

了解优先队列的话，可以构造优先队列，省去每次排序的过程。

 1 class Solution {
 2     public boolean isPossible(int[] target) {
 3         PriorityQueue<Long> que = new PriorityQueue<Long>(target.length, Comparator.reverseOrder());
 4         long sum = 0;
 5         for (long value : target) {
 6             sum += value;
 7             if (value > 1) que.offer(value);
 8         }
 9         while (!que.isEmpty()) {
10             long max = que.poll();
11             long pre_val = (max << 1) - sum;
12             if (pre_val < 1)
13                 return false;
14             else if (pre_val > 1)
15                 que.offer(pre_val);
16             sum = max;
17         }
18         return true;
19     }
20 }

已经可以通过leetcode测试数据，但对于[ $1 0 0 0 0 0 0 0 0 0,1]的极端数值，会超时，针对这种情况进行优化，记录最大值的同时记录次大值，批量更新最大值，直到不大于次大值为止。$

【leetcode】5343. 多次求和构造目标数组

题目描述

思路

推荐阅读