非递增顺序的最小子序列

难度: Easy

给你一个数组 nums，请你从中抽取一个子序列，满足该子序列的元素之和严格大于未包含在该子序列中的各元素之和。

如果存在多个解决方案，只需返回 长度最小 的子序列。如果仍然有多个解决方案，则返回 元素之和最大 的子序列。

与子数组不同的地方在于，「数组的子序列」不强调元素在原数组中的连续性，也就是说，它可以通过从数组中分离一些（也可能不分离）元素得到。

注意，题目数据保证满足所有约束条件的解决方案是唯一的。同时，返回的答案应当按 非递增顺序 排列。

示例 1：

输入：nums = [4,3,10,9,8]
输出：[10,9] 
解释：子序列 [10,9] 和 [10,8] 是最小的、满足元素之和大于其他各元素之和的子序列。但是 [10,9] 的元素之和最大。

示例 2：

输入：nums = [4,4,7,6,7]
输出：[7,7,6] 
解释：子序列 [7,7] 的和为 14 ，不严格大于剩下的其他元素之和（14 = 4 + 4 + 6）。因此，[7,6,7] 是满足题意的最小子序列。注意，元素按非递增顺序返回。

提示：

1 <= nums.length <= 500
1 <= nums[i] <= 100

Submission

运行时间: 27 ms

内存: 16.1 MB

class Solution:
    def minSubsequence(self, nums: List[int]) -> List[int]:
        nums.sort(reverse=True)
        total_sum = sum(nums)
        sub_sum = 0
        for i in range(len(nums)):
            sub_sum += nums[i]
            if sub_sum > total_sum -sub_sum:
                return nums[:i+1]

Explain

本题解采用了排序与累加的方法来寻找最小的子序列，满足子序列的元素之和严格大于未包含在子序列中的元素之和。首先，将数组按照非递增顺序排序，然后从前向后累加元素，同时计算剩余元素的总和。当累加和大于剩余元素的总和时，当前累加的部分即为所求的最小子序列。

时间复杂度: O(n log n)

空间复杂度: O(1)

class Solution:
    def minSubsequence(self, nums: List[int]) -> List[int]:
        nums.sort(reverse=True)  # 将数组降序排序
        total_sum = sum(nums)  # 计算数组总和
        sub_sum = 0  # 初始化子序列的和为0
        for i in range(len(nums)):
            sub_sum += nums[i]  # 累加当前元素到子序列和
            if sub_sum > total_sum - sub_sum:  # 判断子序列和是否大于剩余元素的和
                return nums[:i+1]  # 返回满足条件的最短子序列

Explore

选择进行降序排序的目的是为了尽快地收集到元素总和最大的子序列，从而使得该子序列的和超过剩余部分的总和。如果按升序排序，那么我们将从最小的元素开始累加，这样需要更多的元素才能使子序列的和超过剩余部分，从而导致子序列变长，不满足题目要求的最小子序列。降序排序确保了我们可以尽可能地使用较少的、数值较大的元素来快速达到超过剩余元素总和的目标。

这种做法不会导致忽略更短的子序列。由于数组是降序排序的，最大的元素首先被加入到子序列中。如果我们继续寻找更短的子序列，而不是在累加和首次超过剩余总和时停止，那么由于剩余的元素都比已经选择的元素小，任何尝试用更小的元素替换已经选择的大元素，都将导致需要更多的元素来达到相同的累加和，这与寻找最小子序列的目标相悖。

此条件`sub_sum > total_sum - sub_sum`确保了选取的子序列的和是大于数组剩余部分的和。由于数组是降序排序的，我们能保证当前选择的元素是当前可选的最大元素，从而使得所需的元素数量最小化。这时子序列的长度自然是最短的，同时由于是从最大值开始累加的，所以子序列的和也是最大可能的和。

在此算法中，返回的子序列可能不是唯一的解，尤其是在数组中存在重复元素的情况下。然而，给定的排序和累加的算法流程确保了在这种特定的处理方法（即先排序后累加）下，找到的第一个满足条件的子序列是唯一确定的。如果数组中的元素唯一或者元素的顺序不被改变，那么返回的子序列将是唯一的。如果存在多种可能的子序列满足条件，那么具体的解可能依赖于如何处理等值的元素，例如是否存在多个相同的最大元素可以选择。