题目描述

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

  • 令 x 为你数组里所有元素的和。
  • 选择满足 0 <= i < target.length 的任意下标 i，并让 A 数组中对应下标处的值为 x。

你可以重复该过程任意次。如果能从 A 开始构造出目标数组 target，返回 true，否则返回 false。

例如：target = [9,3,5] → true

  • 初始 A = [1,1,1]，sum = 3，选择下标 0 → A = [3,1,1]，sum = 5
  • 选择下标 2 → A = [3,1,5]，sum = 9
  • 选择下标 0 → A = [9,1,5]，sum = 15
  • 选择下标 1 → A = [9,3,5]，等于 target

例如：target = [1,1,1,2] → false

解题思路

该题的关键是逆向思维：与其从全 1 数组构造 target，不如从 target 反向推导回全 1 数组。

正向 vs 逆向

正向操作：选择 i，将 A[i] 替换为数组总和 sum。这个操作会让选中的元素变大。

逆向操作：在 target 中，最大的元素一定是上一步被替换出来的。因为只有被选中的那个元素才会变成当前数组的总和，它一定大于数组中其他所有元素（其他元素没有被修改，而总和大于任意一个元素）。我们可以将最大的元素 max 还原为上一步的值。

逆向还原规则

假设当前数组的总和为 sum，最大值为 max，其余元素的和为 rest = sum - max。

逆向一步，将 max 还原为它被替换前的值 prev = max - rest（因为替换前数组的总和 = prev + rest，且替换后 max = prev + rest）。

算法步骤

  1. 初始化最大堆，将所有 target 元素插入堆中。同时计算总和 sum。
  2. 循环执行：
    • 从堆中取出最大值 max。
    • 计算剩余元素之和 rest = sum - max。
    • 终止条件一：如果 max == 1 或 rest == 1，说明所有元素都可以回溯到 1，返回 true。
    • 终止条件二（失败）：如果 rest < 1（其余元素和为 0 或负数，不合理）、或者 max <= rest（最大值不大于其余和，意味着逆向无法还原）、或者 max % rest == 0（还原后值为 0，不合理），返回 false。
    • 取模优化：如果不使用取模，最大元素可能需要多次减 rest 才能小于等于其他元素。为了加速，直接用 max % rest 计算下一个值（如果 max % rest == 0 已经在前一步判断过了）。注意如果 max % rest == 0 且 rest == 1 是合法的（因为全 1 数组每一位更新时 rest = sum - 1），不过我们在前一步已通过 rest == 1 返回了 true。
    • 计算 nextVal = max % rest，更新 sum = rest + nextVal，将 nextVal 插入堆中。
  3. 循环最终必然命中终止条件而返回结果。

为什么取模可以优化？

考虑 target = [1, 1000000000]：如果没有取模，将 max 减去 rest 需要 1000000000 / 1 次操作，超时。而使用 max % rest，一步就能计算出最终还原值，极大提高了效率。

复杂度分析

  • 时间复杂度：O(n log n + log M)，其中 n 是数组长度，M 是数组中最大值。建堆 O(n log n)，每次取模操作将一个很大的数至少减半，堆操作次数为 O(log M) 级别，每次 O(log n)。
  • 空间复杂度：O(n)，最大堆存储所有元素。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
package code.J1354;

import datastructure.MyMaxHeap;

public class J1354 {
    public boolean isPossible(int[] target) {
        MyMaxHeap<Long> maxHeap = new MyMaxHeap<>(target.length);
        long sum = 0;
        for (int i : target) {
            sum += i;
            maxHeap.insert((long) i);
        }
        while (true) {
            long max = maxHeap.extractMax();
            long rest = sum - max;
            if (max == 1 || rest == 1) return true;
            if (rest < 1 || max <= rest || max % rest == 0) return false;
            long nextVal = max % rest;
            sum = rest + nextVal;
            maxHeap.insert(nextVal);
        }
    }
}