难度: Medium
Submission
运行时间: 78 ms
内存: 31.6 MB
class Solution: def makePrefSumNonNegative(self, nums: List[int]) -> int: pq = [] s = ans = 0 for x in nums: if x < 0: heappush(pq, x) s += x if s < 0: s -= heappop(pq) ans += 1 return ans
Explain
题解使用了一个最小堆(优先队列)来帮助保持前缀和数组的非负状态。遍历输入数组 `nums`,同时计算前缀和 `s`。对于每个元素 `x`: 1. 如果 `x` 是负数,将其加入最小堆中。 2. 更新前缀和 `s` 为 `s + x`。 3. 如果更新后的前缀和 `s` 小于零,说明当前前缀和包含过多的负数,从堆中弹出一个最小元素(最负的数)并从 `s` 中减去这个值,同时将操作次数 `ans` 加一。这个操作实际上是减少前缀和的负负载,使其回到非负状态。 4. 最终,返回操作次数 `ans`,即最少的次数调整使前缀和非负。这种方法确保了每次调整都是最优的,因为总是移除了前缀和中最大的负数。
时间复杂度: O(n log n)
空间复杂度: O(n)
class Solution: def makePrefSumNonNegative(self, nums: List[int]) -> int: pq = [] # 最小堆,用于存储遇到的负数 s = ans = 0 # 初始化前缀和和操作次数 for x in nums: # 遍历数组 if x < 0: # 如果元素是负数,加入堆 heappush(pq, x) s += x # 更新前缀和 if s < 0: # 如果前缀和为负 s -= heappop(pq) # 移除堆中最小的元素(最负的数),减少前缀和负载 ans += 1 # 增加操作次数 return ans # 返回最少操作次数
Explore
最小堆(优先队列)被选用是因为它能够高效地给出并移除当前所有负数中的最小值(即绝对值最大的负数)。当前缀和变为负数时,我们需要尽可能少地增加前缀和以使其非负。移除最小堆中的最小元素(最负的数)可以最大程度地减少前缀和的负载,从而是调整最高效。如果使用栈或队列,我们只能访问到最近插入的元素,而不是最小值,这会导致我们可能无法以最少的操作次数达成目标,增加了调整的次数和复杂度。
在此算法中,从最小堆中移除的元素确实是前缀和序列中实际出现的负数。算法保证只有当前缀和为负时,才从最小堆中移除元素以调整前缀和。此外,每个负数在加入前缀和时被添加到最小堆中。因此,移除的总是当前堆中存在的、对前缀和负负载贡献最大的负数,这也是实际存在于前缀和序列中的。
如果数组`nums`中所有元素都是正数,那么前缀和`s`从不会变为负数,因此不需要进行任何调整操作,最小堆也不会有元素加入。在这种情况下,算法主要时间消耗来自于遍历数组,时间复杂度为`O(n)`,其中`n`是数组`nums`的长度。