1354. Construct Target Array With Multiple Sums

题目信息

题号:

1354

难度:

Hard

主题:

数组、逆向贪心、优先队列

原题:

LeetCode 1354

重点:

初始数组全为 1;每次把一个位置替换为当前数组总和,判断能否得到目标数组

题目重述

给定正整数数组 target。从同长度、所有元素均为 1 的数组开始,一次操作选择任意下标,把该位置的值替换为操作前整个数组的元素总和。

可以执行任意次数操作。请判断是否能够恰好得到 target。

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

自建示例

按总和反复替换可以构造目标:

输入:target = [5,3]
输出:true
解释:[1,1] -> [2,1] -> [2,3] -> [5,3]。

两个位置同时为二无法从全一数组得到:

输入:target = [2,2]
输出:false
解释:第一次操作只能得到 [2,1] 或 [1,2],之后被替换位置会变为至少 3。