难度: 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`的长度。