Medium

题目描述

给你一个下标从 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 <= 10^5
  • -10^6 <= nums[i] <= 10^6

解题思路

这是一个贪心算法问题。为了使前缀和数组中正数的个数最多，我们需要分析什么样的排列能够产生最优结果。

核心思路：

要让前缀和尽可能多地保持为正数，我们应该：

  1. 优先放置较大的正数：大的正数能为后续的前缀和提供更大的"缓冲"
  2. 将较小的负数放在后面：这样可以延迟前缀和变为负数的时间

算法步骤：

  1. 将数组按降序排序
  2. 计算前缀和，统计有多少个前缀和为正数

正确性证明： 假设存在一个更优的排列，其中某个较小的数 a 排在较大的数 b 前面（a < b）。我们可以交换它们的位置：

  • 交换前：前缀和序列为 ..., S+a, S+a+b, ...
  • 交换后：前缀和序列为 ..., S+b, S+b+a, ...

由于 b > a，交换后的每个前缀和都不会变小，因此正数的个数不会减少。通过反复应用这个交换操作，我们最终得到降序排列是最优的。

时间复杂度主要来自排序操作。

代码实现

class Solution {
public:
    int maxScore(vector<int>& nums) {
        sort(nums.begin(), nums.end(), greater<int>());
        
        long long prefixSum = 0;
        int score = 0;
        
        for (int num : nums) {
            prefixSum += num;
            if (prefixSum > 0) {
                score++;
            }
        }
        
        return score;
    }
};

class Solution:
    def maxScore(self, nums: List[int]) -> int:
        nums.sort(reverse=True)
        
        prefix_sum = 0
        score = 0
        
        for num in nums:
            prefix_sum += num
            if prefix_sum > 0:
                score += 1
        
        return score

public class Solution {
    public int MaxScore(int[] nums) {
        Array.Sort(nums, (a, b) => b.CompareTo(a));
        
        long prefixSum = 0;
        int score = 0;
        
        foreach (int num in nums) {
            prefixSum += num;
            if (prefixSum > 0) {
                score++;
            }
        }
        
        return score;
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxScore = function(nums) {
    nums.sort((a, b) => b - a);
    
    let prefixSum = 0;
    let score = 0;
    
    for (let num of nums) {
        prefixSum += num;
        if (prefixSum > 0) {
            score++;
        }
    }
    
    return score;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log n)主要是排序的时间复杂度，其中 n 为数组长度
空间复杂度O(1)只使用了常数额外空间（不考虑排序的空间开销）

相关题目