leetcode
leetcode 2251 ~ 2300
使前缀和数组非负

使前缀和数组非负

难度:

标签:

题目描述

代码结果

运行时间: 78 ms, 内存: 31.6 MB


/*
 * 思路:
 * 使用Java Stream API来实现上述逻辑。我们可以使用一个AtomicInteger来追踪前缀和,
 * 并在遍历过程中根据前缀和的值调整每个元素。
 */
import java.util.concurrent.atomic.AtomicInteger;
import java.util.stream.IntStream;

public class Solution {
    public int[] makePrefSumNonNegative(int[] nums) {
        AtomicInteger prefixSum = new AtomicInteger(0);
        return IntStream.of(nums)
            .map(num -> {
                int currentSum = prefixSum.addAndGet(num);
                while (currentSum < 0) {
                    num++;
                    currentSum = prefixSum.incrementAndGet();
                }
                return num;
            })
            .toArray();
    }
}

解释

方法:

题解使用了一个最小堆(优先队列)来帮助保持前缀和数组的非负状态。遍历输入数组 `nums`,同时计算前缀和 `s`。对于每个元素 `x`: 1. 如果 `x` 是负数,将其加入最小堆中。 2. 更新前缀和 `s` 为 `s + x`。 3. 如果更新后的前缀和 `s` 小于零,说明当前前缀和包含过多的负数,从堆中弹出一个最小元素(最负的数)并从 `s` 中减去这个值,同时将操作次数 `ans` 加一。这个操作实际上是减少前缀和的负负载,使其回到非负状态。 4. 最终,返回操作次数 `ans`,即最少的次数调整使前缀和非负。这种方法确保了每次调整都是最优的,因为总是移除了前缀和中最大的负数。

时间复杂度:

O(n log n)

空间复杂度:

O(n)

代码细节讲解

🦆
为什么选择使用最小堆来存储负数,而不是其他数据结构如栈或队列?
最小堆(优先队列)被选用是因为它能够高效地给出并移除当前所有负数中的最小值(即绝对值最大的负数)。当前缀和变为负数时,我们需要尽可能少地增加前缀和以使其非负。移除最小堆中的最小元素(最负的数)可以最大程度地减少前缀和的负载,从而是调整最高效。如果使用栈或队列,我们只能访问到最近插入的元素,而不是最小值,这会导致我们可能无法以最少的操作次数达成目标,增加了调整的次数和复杂度。
🦆
在从最小堆中移除元素时,是否有可能移除的不是当前前缀和序列中实际出现的负数?
在此算法中,从最小堆中移除的元素确实是前缀和序列中实际出现的负数。算法保证只有当前缀和为负时,才从最小堆中移除元素以调整前缀和。此外,每个负数在加入前缀和时被添加到最小堆中。因此,移除的总是当前堆中存在的、对前缀和负负载贡献最大的负数,这也是实际存在于前缀和序列中的。
🦆
如果数组`nums`全为正数,算法的时间复杂度是多少?
如果数组`nums`中所有元素都是正数,那么前缀和`s`从不会变为负数,因此不需要进行任何调整操作,最小堆也不会有元素加入。在这种情况下,算法主要时间消耗来自于遍历数组,时间复杂度为`O(n)`,其中`n`是数组`nums`的长度。

相关问题