LeetCode 题解工作台
重排数组以得到最大前缀分数
给你一个下标从 0 开始的整数数组 nums 。你可以将 nums 中的元素按 任意顺序 重排（包括给定顺序）。 令 prefix 为一个数组，它包含了 nums 重新排列后的前缀和。换句话说， prefix[i] 是 nums 重新排列后下标从 0 到 i 的元素之和。 nums 的 分数 是 p…
4
题型
6
代码语言
3
相关题
当前训练重点
中等 · 贪心·invariant
答案摘要
要使得前缀和数组中正整数的个数最多，就要使得前缀和数组中的元素尽可能大，即尽可能多的正整数相加。因此，我们可以将数组 降序排序，然后遍历数组，维护前缀和 ，如果 $s \leq 0$，则说明当前位置以及之后的位置都不可能再有正整数，因此直接返回当前位置即可。 否则，遍历结束后，返回数组长度。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 贪心·invariant 题型思路
题目描述
给你一个下标从 0 开始的整数数组 nums 。你可以将 nums 中的元素按 任意顺序 重排（包括给定顺序）。
令 prefix 为一个数组，它包含了 nums 重新排列后的前缀和。换句话说，prefix[i] 是 nums 重新排列后下标从 0 到 i 的元素之和。nums 的 分数 是 prefix 数组中正整数的个数。
返回可以得到的最大分数。
示例 1：
输入：nums = [2,-1,0,1,-3,3,-3] 输出：6 解释：数组重排为 nums = [2,3,1,-1,-3,0,-3] 。 prefix = [2,5,6,5,2,2,-1] ，分数为 6 。 可以证明 6 是能够得到的最大分数。
示例 2：
输入：nums = [-2,-3,0] 输出：0 解释：不管怎么重排数组得到的分数都是 0 。
提示：
1 <= nums.length <= 105-106 <= nums[i] <= 106
解题思路
方法一：贪心 + 排序
要使得前缀和数组中正整数的个数最多，就要使得前缀和数组中的元素尽可能大，即尽可能多的正整数相加。因此，我们可以将数组 降序排序，然后遍历数组，维护前缀和 ，如果 ，则说明当前位置以及之后的位置都不可能再有正整数，因此直接返回当前位置即可。
否则，遍历结束后，返回数组长度。
时间复杂度 ，空间复杂度 。其中 为数组 的长度。
class Solution:
def maxScore(self, nums: List[int]) -> int:
nums.sort(reverse=True)
s = 0
for i, x in enumerate(nums):
s += x
if s <= 0:
return i
return len(nums)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n log n) due to sorting, and space complexity is O(1) or O(n) depending on whether a separate prefix array is maintained. Iteration and cumulative sum tracking are linear operations. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Expect candidates to identify the greedy choice of ordering the array in descending values.
- question_mark
Look for correct handling of prefix sums to avoid early negative totals that reduce score.
- question_mark
Watch if candidates can justify why adding smaller elements later does not reduce maximum score.
常见陷阱
外企场景- error
Adding elements without checking if the running prefix sum remains positive.
- error
Failing to sort in descending order, which can lower the maximum achievable score.
- error
Miscounting prefix sum positions when updating the score.
进阶变体
外企场景- arrow_right_alt
Compute the minimum number of negative prefix sums achievable with any rearrangement.
- arrow_right_alt
Find the rearrangement that maximizes the sum of all positive prefix sums instead of count.
- arrow_right_alt
Handle arrays with additional constraints like only rearranging subsets of the elements.