求最少元素移至数组末尾使所有前缀和非负的最优算法

问题描述 #

给定一个整数数组，「移动」操作定义为删除单个元素并将其放置到数组末尾。要求找到最少的移动次数，使得调整后数组的所有前缀和均为非负。题目保证一定存在合法的调整方案。

示例 #

• 示例1：输入[1,3,-4,1]，输出0。所有前缀和为1、4、0、1，全部非负，无需移动。
• 示例2：输入[1,3,-5,1]，输出1。移动-5到末尾得到[1,3,1,-5]，所有前缀和均满足要求。
• 示例3：输入[15,-10,-11,1,-7,12]，输出2。移动-11和-10到末尾得到[15,1,-7,12,-11,-10]，所有前缀和符合要求。

最优解法思路 #

要得到最少移动次数，等价于尽可能多地保留元素在数组前半段、无需移动，且这些保留元素按原顺序排列的所有前缀和均为非负，剩下的元素统一移动到末尾即可。
我们采用贪心+最小堆的策略实现：

1. 顺序遍历数组，维护当前保留元素的前缀和current_sum，同时用最小堆存储所有已保留的负数元素。
2. 每遍历到一个元素，先将其加到current_sum中，若该元素为负数则压入最小堆。
3. 若此时current_sum变为负数，说明当前保留的元素中存在绝对值过大的负数，导致前缀和不符合要求。我们弹出堆顶最小的负数（绝对值最大的负数），将其计入移动集合，同时把该数从current_sum中扣除（相当于取消保留该元素，前缀和加回对应绝对值），移动次数加1，重复操作直到current_sum回到非负。
   该策略的核心逻辑是：每次移除对前缀和负面影响最大的元素，用最少的移除次数让前缀和恢复合法，保证保留的元素数量最多。

代码实现（Python） #

import heapq

def min_moves(nums):
    current_sum = 0
    move_count = 0
    min_heap = []
    for num in nums:
        current_sum += num
        if num < 0:
            heapq.heappush(min_heap, num)
        # 当前前缀和非法，移除影响最大的负数
        while current_sum < 0:
            smallest_neg = heapq.heappop(min_heap)
            current_sum -= smallest_neg
            move_count += 1
    return move_count

复杂度说明 #

• 时间复杂度：O(n log n)，每个元素最多入堆、出堆各1次，每次堆操作的时间复杂度为O(log n)，是该问题的时间复杂度最优解法。
• 空间复杂度：O(n)，最坏情况所有元素均为负数，堆需要存储全部元素。

内容的提问来源于stack exchange，提问作者guruguru