LeetCode 题解工作台
非递增顺序的最小子序列
给你一个数组 nums ，请你从中抽取一个子序列，满足该子序列的元素之和 严格 大于未包含在该子序列中的各元素之和。 如果存在多个解决方案，只需返回 长度最小 的子序列。如果仍然有多个解决方案，则返回 元素之和最大 的子序列。 与子数组不同的地方在于，「数组的子序列」不强调元素在原数组中的连续性，也…
3
题型
6
代码语言
3
相关题
当前训练重点
简单 · 贪心·invariant
答案摘要
我们可以先对数组 按照从大到小的顺序排序，然后依次从大到小加入数组中的元素，每次加入后判断当前元素之和是否大于剩余元素之和，如果大于则返回当前数组。 时间复杂度 $O(n \times \log n)$，空间复杂度 $O(\log n)$。其中 是数组 的长度。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 贪心·invariant 题型思路
题目描述
给你一个数组 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 <= 5001 <= nums[i] <= 100
解题思路
方法一：排序
我们可以先对数组 按照从大到小的顺序排序，然后依次从大到小加入数组中的元素，每次加入后判断当前元素之和是否大于剩余元素之和，如果大于则返回当前数组。
时间复杂度 ，空间复杂度 。其中 是数组 的长度。
class Solution:
def minSubsequence(self, nums: List[int]) -> List[int]:
ans = []
s, t = sum(nums), 0
for x in sorted(nums, reverse=True):
t += x
ans.append(x)
if t > s - t:
break
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Did the candidate utilize sorting as part of their approach?
- question_mark
How well does the candidate handle greedy choice plus invariant validation?
- question_mark
Does the candidate explain the optimality of their solution in terms of both subsequence size and sum?
常见陷阱
外企场景- error
Forgetting to sort the array in non-increasing order, which leads to incorrect subsequences.
- error
Not maintaining the running sums of the subsequence and the remaining elements, which may result in an incorrect conclusion about when to stop.
- error
Returning a subsequence that isn't sorted correctly in non-increasing order, which is a key requirement.
进阶变体
外企场景- arrow_right_alt
Consider the case where there are duplicate values in the array. Does the approach handle duplicates correctly?
- arrow_right_alt
What happens if there is only one element in the array? Ensure the solution works in edge cases.
- arrow_right_alt
Can this approach be modified for arrays with negative values or different constraints?