问题描述
Given an array of integers target. From a starting array, A consisting of all 1’s, you may perform the following procedure :
let x be the sum of all elements currently in your array. choose index i, such that 0 <= i < target.size and set the value of A at index i to x. You may repeat this procedure as many times as needed. Return True if it is possible to construct the target array from A otherwise return False.
Example 1:
Input: target = [9,3,5]
Output: true
Explanation: Start with [1, 1, 1]
[1, 1, 1], sum = 3 choose index 1
[1, 3, 1], sum = 5 choose index 2
[1, 3, 5], sum = 9 choose index 0
[9, 3, 5] Done
Example 2:
Input: target = [1,1,1,2]
Output: false
Explanation: Impossible to create target array from [1,1,1,1].
Example 3:
Input: target = [8,5]
Output: true
Constraints:
- N == target.length
- 1 <= target.length <= 5 * 10^4
- 1 <= target[i] <= 10^9
Hint 1: Given that the sum is strictly increasing, the largest element in the target must be formed in the last step by adding the total sum in the previous step. Thus, we can simulate the process in a reversed way.
Hint 2: Subtract the largest with the rest of the array, and put the new element into the array. Repeat until all elements become one
问题分析
刚拿到问题时，由于暂时没有特别理想的思路，便先尝试使用“模拟”法求解：即用代码模拟题目描述的计算过程，如果能在时限内解决，再尝试去优化求解过程。
首先我们将target数组排序，方便依次计算；然后从1开始，按照提示方法不断加和；如果在循环过程中，加和结果等于当前数组元素，则继续迭代下一个待计算元素；如果超过当前元素，则表明无法生成该元素。
但是实际运行后，发现这种算法是错误的，对于 [5, 8] 这样的一个test case并不能通过：
我们逐步分析下模拟过程:
[1, 1] // 初始状态
[2, 1] // 不断累加更新第一个元素
[3, 1]
[4, 1]
[5, 1] // 至此，第一个元素满足，开始计算第二个元素
[5, 6]
[5, 11] // 超出目标值，返回false
而正确的过程为:
[1, 1] // 初始状态
[2, 1] // 累加更新第一个元素
[2, 3] // 累加更新第二个元素
[5, 3] // 累加更新第一个元素
[5, 8] // 累加更新第二个元素
至此，模拟方式行不通；查看提示后，题目让我们逆向去模拟计算过程。仔细考虑一下，为什么正向模拟行不通，而逆向模拟就可以呢？原因在于，每次更新一个值时，这个值一定是当前状态下的最大值。如果target数组是可以被某种方式成功构建出来，那么我们逆向的处理之后，每次处理的元素就是当前状态下的最大值，也就能找到正确处理顺序的逆序；最终得到一个全是1的数组
这里有一点需要注意的是，题目提示中让我们逐步的进行减操作，这个其实有坑，对于[1, 1000000000]这样的test case会TLE；所以这里我们需要用取模操作代替减操作，来减少计算的次数
另外，为了能快速拿到过程中数组的最大值，我们还需要维护一个最大堆
示例代码
func isPossible(target []int) bool {
if len(target) == 1 {
return target[0] == 1
}
heap := maxheap{}
sum := 0
rest := 0
// 将元素都添加到堆中，并计算数组和
for _, v := range target {
heap.Add(v)
sum += v
}
for {
// 当前堆顶元素
top := heap.Top()
// 当前数组中除堆顶元素外，其他元素的和
rest = sum - top
// 如果堆顶元素已经是1 或者 剩余元素和是1 则满足条件，直接返回
if top == 1 || rest == 1 {
return true
}
// 如果堆顶元素已经小于1 或者小于剩余元素和，说明不满足条件，返回false
if top < 1 || top <= rest {
return false
}
// 堆顶元素取余
newtop := top % rest
if newtop == 0 {
return false
}
// 更新当前数组和
sum = sum - top + newtop
// 更新堆顶元素
heap.list[0] = newtop
// 重新堆化
heap.adjustFromTop()
}
}
type maxheap struct {
list []int
}
// 添加元素
func (m *maxheap) Add(val int) {
m.list = append(m.list, val)
m.adjustFromBottom()
}
// 返回堆顶元素
func (m *maxheap) Top() int {
if len(m.list) == 0 {
return -1
}
return m.list[0]
}
// 自底向上堆化
func (m *maxheap) adjustFromBottom() {
idx := len(m.list) - 1
for {
if idx == 0 {
break
}
swapidx := (idx - 1) / 2
if swapidx < 0 {
break
}
if m.list[swapidx] >= m.list[idx] {
break
}
m.list[idx], m.list[swapidx] = m.list[swapidx], m.list[idx]
idx = swapidx
}
}
// 自顶向下堆化
func (m *maxheap) adjustFromTop() {
root := 0
swapidx := root
for {
left := 2*swapidx + 1
if left < len(m.list) && m.list[swapidx] < m.list[left] {
swapidx = left
}
right := left + 1
if right < len(m.list) && m.list[swapidx] < m.list[right] {
swapidx = right
}
if swapidx == root {
break
}
m.list[root], m.list[swapidx] = m.list[swapidx], m.list[root]
root = swapidx
}
}